Mèo ~Tesdizz~ vừa trải qua kì kiểm tra cuối kì ~II~ đầy cam go. Để đạt được học bổng thì điểm trung bình tất cả các môn phải lớn hơn hoặc bằng ~avg~, nghĩa là với ~n~ bài kiểm tra có điểm là ~a_1, a_2, a_3, ..., a_n~ để có học bổng phải thỏa ~\frac{a_1+a_2+a_3+...+a_n}{n} \ge avg~ . Sau khi điểm của kì kiểm tra được công bố thì các thí sinh có thể viết bài luận giúp cải thiện điểm cho bài thi của mình.
Kì kiểm tra học kì ~II~ gồm ~n~ bài được đánh số từ ~1~ đến ~n~ và điểm tối đa của mỗi bài kiểm tra là ~10~. Với bài kiểm tra thứ ~i~ (chưa đạt điểm tối đa), mỗi lần cải thiện điểm ta cần viết ~b_i~ bài luận giúp cho điểm bài kiểm tra thứ ~i~ tăng ~1~ điểm. Vì số tiền học bổng rất hấp dẫn nên mèo ~Tesdizz~ quyết tâm phải giành lấy, các bạn hãy giúp mèo ~Tesdizz~ tính toán xem cần viết ít nhất bao nhiêu bài luận để đạt được học bổng nhé!
Lưu ý: mỗi bài kiểm tra chỉ được cải thiện điểm tối đa ~1~ lần.
Dữ liệu vào
- Dòng thứ nhất chứa hai số nguyên ~n~, ~avg~ (~1 \le n \le 10^5, 1 \le avg \le 10~) lần lượt là số bài kiểm tra và số điểm trung bình tối thiểu để đạt học bổng.
- ~N~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~a_i, b_i~ (~0 \le a_i \le 10, 1 \le b_i \le 10^6~) lần lượt là điểm và số bài luận cần viết cho bài kiểm tra thứ ~i~.
Kết quả ra
Một dòng duy nhất chứa số bài luận tối thiểu cần viết. Nếu không có cách nào đạt được học bổng thì in ra khong the
.
Ràng buộc
- Có ~40\%~ số điểm ứng với ~n \le 10^3~.
- Có ~60\%~ số điểm ứng với ~n \le 10^5~.
Ví dụ 1
Dữ liệu
5 4
5 2
4 7
3 1
3 2
2 5
Kết quả
5
Giải thích
Ta chọn cải thiện bài kiểm tra thứ 1, 3, 4.
Ví dụ 2
Dữ liệu
2 4
5 2
5 2
Kết quả
0
Bình luận