Ukrayna'da şehir ve yol var. Bağımsızlığın . yıl dönümünde bunu düzeltmenin zamanı geldi.
Şehirler arasında n-1 yol inşa etmek istiyorsunuz; öyle ki bu yollar üzerinden her şehirden diğer herhangi bir şehre gidilebilsin. ve şehirleri arasına yol inşa etmenin maliyeti bütçe kaynaklarından (a_i + a_j)\bmod M milyon grivnadır; burada — Ukrayna'nın mevcut Cumhurbaşkanı'nın en sevdiği sayıdır.
Bu planı gerçekleştirmek için bütçe kaynaklarından en az kaç milyon grivna gereklidir?
İlk satır iki tam sayı , (1 \le n \le 200000, 1 \le M \le 10^9) içerir — sırasıyla şehirlerin sayısı ve Ukrayna'nın mevcut Cumhurbaşkanı'nın en sevdiği sayı.
İkinci satır tam sayı a_1, a_2, \ldots, a_n (0 \le a_i < M) içerir.
Her şehirden diğer herhangi bir şehre gidilebilecek şekilde n-1 yol inşa etmek için harcanması gereken en az bütçe kaynağı miktarını milyon grivna cinsinden yazdırın.
Örnek 1
Örnek 2
Örnek 3
Örnek 4
İlk örnekte aşağıdaki maliyetlerle yol inşa edebiliriz:
, şehirleri arasında: (42 + 69)\bmod 350 = 111
, şehirleri arasında: (42 + 300)\bmod 350 = 342
, şehirleri arasında: (69 + 300)\bmod 350 = 19
En iyisi ve yollarını seçmektir, toplam maliyeti 111+19 = 130 olur.