Ukraynada şəhər və yol var. Müstəqilliyin illiyinə qədər bunu düzəltməyin vaxtıdır.
Siz şəhərlər arasında n-1 yol çəkmək istəyirsiniz ki, onların vasitəsilə hər şəhərdən istənilən digər şəhərə getmək mümkün olsun. və şəhərləri arasında yol çəkməyin dəyəri büdcə vəsaitlərindən (a_i + a_j)\bmod M milyon qrivnadır, burada — Ukraynanın hazırkı Prezidentinin sevimli ədədidir.
Bu planı həyata keçirmək üçün büdcə vəsaitlərindən ən azı neçə milyon qrivna lazımdır?
Birinci sətirdə iki tam ədəd , (1 \le n \le 200000, 1 \le M \le 10^9) — uyğun olaraq şəhərlərin sayı və Ukraynanın hazırkı Prezidentinin sevimli ədədi verilir.
İkinci sətirdə tam ədəd a_1, a_2, \ldots, a_n (0 \le a_i < M) verilir.
Hər şəhərdən istənilən digər şəhərə getmək mümkün olacaq şəkildə n-1 yol çəkmək üçün xərclənməli olan büdcə vəsaitlərinin ən az milyon qrivna miqdarını çap edin.
Nümunə 1
Nümunə 2
Nümunə 3
Nümunə 4
Birinci nümunədə biz aşağıdakı dəyərlərlə yol çəkə bilərik:
, şəhərləri arasında: (42 + 69)\bmod 350 = 111
, şəhərləri arasında: (42 + 300)\bmod 350 = 342
, şəhərləri arasında: (69 + 300)\bmod 350 = 19
Ən sərfəlisi və yollarını seçməkdir, onların ümumi dəyəri 111+19 = 130.