Qidiruv
Qidiruv-04
Qidiruv-05
TwoPtr-01
~/algor $ cat masalalar/qidiruv-daraxt-kesish
Qidiruv-05
Daraxtlarni kesish
Muallif:
Iqbolshoh Ilhomjonov
Qiyin
1000 ms
128 MB
81%
O'rmonchiga $m$ metr yog'och kerak. Qatorda $n$ ta daraxt bor, $i$-sining balandligi $a_{i}$. U arrani butun $H \ge 0$ balandlikka o'rnatadi: $H$ dan baland har bir daraxtning $H$ dan yuqori qismi kesib olinadi ($a_{i} - H$ metr), boshqa daraxtlarga tegilmaydi. Kamida $m$ metr yog'och olinadigan $H$ ning eng katta qiymatini toping.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita natural son: $n$ va $m$. Ikkinchi qatorda bo'sh joy bilan ajratilgan $n$ ta natural son $a_{i}$.
Chiquvchi ma'lumotlar
Bitta butun son — $H$ ning eng katta qiymati.
Izoh
$1 \le n \le 10^{5}$
$1 \le a_{i} \le 10^{9}$
$1 \le m \le a_{1} + a_{2} + \dots + a_{n} \le 10^{14}$
Misollar
Kirish #1
4 7 20 15 10 17
Chiqish #1
15
Kirish #2
3 6 5 5 5
Chiqish #2
3