Son Derece Özgün Bir Kapsayan Ağaç Problemi#12856

Son Derece Özgün Bir Kapsayan Ağaç Problemi

3 saniye
256 megabayt
Çok zor

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?

Giriş

İ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.

Çıktı

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.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Örnek 3

Loading
Loading

Örnek 4

Loading
Loading

Not

İ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.