Codeforces Round #696 (Div. 2)
13:03:53 |
C. Ваня ба шалгалт
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Ваня $n$ шалгалт өгч их сургуулийн тэтгэлэг авахыг хүсэж байгаа. Хэрвээ бүх шалгалтын онооны дундаж нь хамгийн багадаа $avg$ байвал тэр тэтгэлэг авна. Шалгалт бүрээс авах оноо нь $r$-ээс хэтрэхгүй. Ванягийн өгсөн шалгалтын оноонууд мэдэгдэж байгаа ба $i$-р шалгалтын дүн $a_{i}$ юм. Ваня $i$-р шалгалтын оноог $1$-ээр ихэсгэхийн тулд $b_{i}$ эссэ бичих ёстой. Тэр шалгалтын оноогоо олон удаа ихэсгэж чадна.
Ваня тэтгэлэг авахын тулд хамгийн багадаа хэдэн ширхэг эссэ бичих вэ?
Оролт
Эхний мөр нь гурван бүхэл $n$, $r$, $avg$ ($1 ≤ n ≤ 10^{5}$, $1 ≤ r ≤ 10^{9}$, $1 ≤ avg ≤ min(r, 10^{6})$) тоонуудыг агуулна. Эдгээр нь харгалзан шалгалтын тоо, хамгийн их оноо болон шаардлагатай дундаж оноо юм.
Дараагийн $n$ мөрөнд зайгаар тусгаарлагдсан бүхэл $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i} ≤ r$, $1 ≤ b_{i} ≤ 10^{6}$) тоонууд агуулагдана.
Гаралт
Эхний мөрөнд бичих шаардлагатай эссэнүүдийн хамгийн бага тоог хэвлэнэ.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
5 5 4 5 2 4 7 3 1 3 2 2 5
Гаралт
4
Оролт
2 5 4 5 2 5 2
Гаралт
0
Тэмдэглэл
Эхний жишээнд, Ваня $2$ эссэ бичиж $3$ дахь шалгалтын дүнгээ $2$ оноогоор ихэсгэх ба $4$ дэхь шалгалтын дүнгээ $1$ оноогоор ихэсгэхийн тулд $2$ эссэ бичнэ.
Хоёр дахь жишээнд, Ваня ямар ч эссэ бичих хэрэггүй учир нь түүний дундаж оноо шаардлагатай онооноос аль хэдийн их байгаа.