Problem
Tom Sawyer, Polly Teyzenin evini çevreleyen çiti boyamak gibi zor bir görevde kendisine yardım etmeleri için n kadar arkadaşını ikna etti. Çit, 1'den k'ye kadar numaralandırılmış k ardışık panolardan oluşur ve k'inci panodan sonra yine ilki gelir.
Tom'un arkadaşları çok titizdir, i'inci arkadaş, yalnızca ardışık tüm panoların bir bölümünü boyamasına izin verilirse resme katılmayı kabul eder. Tom'un yalnızca bir fırçası var, bu yüzden arkadaşları sırayla boyayacak ve tüm bölüm onlara tahsis edilecek. Tom'un yapması gereken tek şey, arkadaşlarını davet etme sırasını seçmek ve her biri için istenen ardışık pano sayısını seçmek.
Aynı zamanda, Tom'un arkadaşlarından her biri hem boyanmamış bir çit tahtasını hem de seleflerinden biri tarafından zaten boyanmış olan bir tahtayı boyamaya hazır. Ancak arkadaşlar boyanmamış bir tahtayı boyamaktan daha çok keyif alıyorlar. Tom bir x sayısı seçmek ve boyanacak çit bölümlerini, arkadaşlarının her biri en az x boyanmamış kalas boyayacak şekilde dağıtmak istiyor. Tom arkadaşlarını çok seviyor ve her birinin çiti boyamaktan en iyi şekilde yararlanmasını istiyor, bu yüzden x'i maksimize etmeye çalışıyor.
Tom'un arkadaşlarına ne kadar neşe getirebileceğini anlamasına yardım et.
Giriş verisi biçimi
Girdi dosyasının ilk satırı iki tamsayı içerir n (1 ≤ n ≤ 10
5 ) ve k (1 ≤ k ≤ 10
9 ). Sonraki satır n tamsayı içeriyor — a
i değerleri (1 ≤ a
i ≤ k).
Çıktı verisi biçimi
Bir sayı yazdır —
x maksimum olası değeri.
| Giriş |
Çıktı |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
Açıklama
İlk örnekte x = 5 çünkü arkadaşlardan biri beşten fazla tahta boyamak istemiyor. Önce o gelecek, beşini boyayacak, ardından boyanmamış 10 tahta daha Tom'un ikinci arkadaşına gidecek. Kalan 85 panonun Tom'un kendisi tarafından boyanması gerekecek.
İkinci örnekte x = 2 örneğine şu şekilde ulaşılabilir. İlk olarak, üçüncü arkadaş 4'ten 6'ya kadar tahtaları boyar (3 boyanmamış tahta). Daha sonra dördüncü arkadaş 1'den 5'e kadar olan panoları boyar (3 adet boyasız pano). Sonra ikinci arkadaş 1'den 8'e kadar tahtaları boyar (2 boyanmamış tahta). Son olarak, ilk arkadaş 6'dan 10'a ve 1'den 2'ye kadar tahtaları boyar (boyasız 2 tahta, çitin bir döngü içinde gittiğine ve bu tahtaların ardışık bir parça oluşturduğuna dikkat edin).