Son dərəcə orijinal örtən ağac məsələsi#12856

Son dərəcə orijinal örtən ağac məsələsi

3 saniyə
256 meqabayt
Çox çətin

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?

Giriş

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.

Çıxış

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ələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Nümunə 3

Loading
Loading

Nümunə 4

Loading
Loading

Qeyd

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.