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$ эссэ бичнэ.

Хоёр дахь жишээнд, Ваня ямар ч эссэ бичих хэрэггүй учир нь түүний дундаж оноо шаардлагатай онооноос аль хэдийн их байгаа.

Сэтгэгдлүүдийг ачааллаж байна...