Tí tốt nghiệp Đại học Nông nghiệp, bạn ấy quyết định về quê để phát triển sự nghiệp. Sau hợn một năm vất vả, Tí đã có một khu vườn với n cây, cây thứ i có sức sống hiện tại là ai và khả năng phát triển là bi.
Tí dự định sử dụng tổng cộng L lít nước để tưới cho các cây trong vườn. Với mỗi lít nước tưới vào một cây thứ i, sức sống của cây sẽ tăng thêm bi. Ngoài ra, số lít nước tưới vào mỗi cây phải là số nguyên. Tí đánh giá vẻ đẹp của khu vườn là sức sống bé nhất trong số n cây trong vườn.
Yêu cầu: Hãy giúp bạn ấy tìm cách tưới nước sao cho sức sống của khu vườn là lớn nhất có thể.
Dữ liệu vào:
- Dòng thứ nhất ghi hai số nguyên n, L (1 ≤ n ≤ 105, 1 ≤ L ≤ 109) lần lượt là số cây và số lít nước dùng để tưới cây.
- n dòng tiếp theo, dòng thứ i gồm hai số nguyên ai và bi (1 ≤ ai, bi ≤ 104) lần lượt là sức sống và khả năng phát triển của cây thứ i.
Dữ liệu ra: Ghi ra vẻ đẹp lớn nhất có thể của khu vườn với cách tưới cây tối ưu.
|
GARDEN.INP |
GARDEN.OUT |
|
1 5 3 2 |
13 |
|
3 5 1 5 6 2 3 3 |
8 |
|
2 10 100 1 10 2 |
30 |
Giải thích:
- Ở Test 1, ta sẽ tưới 5 lít nước vào cây duy nhất trong vườn. Khi đó, sức sống của cây trở thành 3 + 5 * 2 = 13, đây cũng là vẻ đẹp của khu vườn.
- Ở Test 2, ta sẽ tưới 2 lít nước vào cây thứ nhất, 1 lít nước vào cây thứ hai và 2 lít nước vào cây thứ 3. Khi đó, sức sống của các cây lần lượt là [11, 8, 9] và vẻ đẹp của khu vườn là 8.
- Ở Test 3, ta sẽ tưới cả 10 lít nước vào cây thứ hai. Khi đó, sức sống của các cây lần lượt là [100, 30] và vẻ đẹp của khu vườn là 30.
Ràng buộc:
- Subtask 1 (30% số test): n, L < 1000
- Subtask 2 (30% số test): L < 105
- Subtask 3 (40% số test): Không có ràng buộc gì thêm