Problem
Tom Sawyer memujuk rakan-rakannya untuk membantunya dalam tugas sukar mengecat pagar yang mengelilingi rumah Mak Cik Polly. Pagar terdiri daripada k papan berturut-turut, bernombor dari 1 hingga k, dan selepas papan ke-k muncul lagi yang pertama.
Rakan-rakan Tom sangat cerewet, rakan ke-i bersetuju untuk mengambil bahagian dalam melukis hanya jika dia dibenarkan melukis bahagian tepat ai papan berturut-turut. Tom hanya mempunyai satu berus, jadi rakan-rakannya akan melukis secara bergilir-gilir dan sekaligus keseluruhan segmen diperuntukkan kepada mereka. Satu-satunya perkara yang perlu dilakukan Tom ialah memilih susunan untuk menjemput rakan-rakannya, serta memilih bilangan papan berturut-turut yang diingini untuk setiap satu.
Pada masa yang sama, setiap rakan Tom bersedia untuk melukis kedua-dua papan pagar yang tidak dicat dan papan yang telah dicat oleh salah seorang pendahulunya. Walau bagaimanapun, rakan-rakan mendapat lebih keseronokan daripada mengecat papan yang tidak dicat. Tom ingin memilih nombor x dan mengagihkan bahagian pagar untuk dicat sedemikian rupa sehingga setiap rakannya melukis sekurang-kurangnya x papan yang tidak dicat. Tom sangat menyayangi rakan-rakannya dan mahu setiap daripada mereka mendapat yang terbaik daripada mengecat pagar, jadi dia cuba memaksimumkan x.
Bantu Tom memahami betapa gembiranya dia dapat membawa kepada rakan-rakannya.
Format data input
Baris pertama fail input mengandungi dua integer n (1 ≤ n ≤ 10
5 ) dan k (1 ≤ k ≤ 10
9 ). Baris seterusnya mengandungi n integer — nilai a
i (1 ≤ a
i ≤ k).
Format data output
Cetak satu nombor — nilai maksimum yang mungkin bagi
x.
| Input |
Output |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
Penjelasan
Dalam contoh pertama x = 5 kerana salah seorang rakan hanya tidak mahu melukis lebih daripada lima papan. Dia akan datang dahulu, mengecat limanya, selepas itu 10 lagi papan yang tidak dicat akan pergi kepada rakan kedua Tom. Baki 85 papan perlu dicat oleh Tom sendiri.
Dalam contoh kedua, x = 2 boleh dicapai, contohnya, seperti ini. Pertama, rakan ketiga melukis papan 4 hingga 6 (3 papan yang tidak dicat). Kemudian rakan keempat melukis papan 1 hingga 5 (3 papan yang tidak dicat). Kemudian rakan kedua melukis papan 1 hingga 8 (2 papan yang tidak dicat). Akhir sekali, rakan pertama mengecat papan 6 hingga 10 dan 1 hingga 2 (2 papan yang tidak dicat, ambil perhatian bahawa pagar berjalan dalam kitaran dan papan ini membentuk segmen berturut-turut).