Nam sở hữu một khu vườn có trồng ~n~ cây, cây thứ ~i~ có độ tươi tốt hiện tại ~a_i~ và khả năng tăng trưởng ~b_i~.

Hôm nay, Nam 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~, độ tươi tốt của cây sẽ tăng thêm ~b_i~. Ngoài ra, số lít nước tưới vào mỗi cây phải là số nguyên.

Nam đánh giá vẻ đẹp của khu vườn là độ tươi tốt bé nhất trong số ~n~ cây trong vườn. Hãy giúp Nam tìm cách tưới nước sao cho vẻ đẹp của khu vườn là lớn nhất có thể.

Dữ liệu

• Dòng thứ nhất ghi hai số nguyên ~n,L(1≤n≤10^5,1≤L≤10^9)~ – số cây trong vườn và số lít nước dùng để tưới cây.
• ~n~ dòng tiếp theo, dòng thứ ~i~ gồmh ~a_i~ số nguyên ~a_i~ và ~b_i (1≤a_i,b_i ≤10^4)~- độ tươi tốt và khả năng tăng trưởng của cây thứ ~i~

Kết quả

• In 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.

Ví dụ

Sample Input 1

1 5
3 2

Sample Output 1

13

Sample Input 2

3 5
1 5
6 2
3 3

Sample Output 2

8

Sample Input 3

2 10
100 1
10 2

Sample Output 3

30

Giải thích

• Ở ví dụ thứ nhất, ta sẽ tưới ~5~ lít nước vào cây duy nhất trong vườn. Khi đó, độ tươi tốt của cây trở thành ~3 + 5 ∗ 2 = 13~, và đây cũng là vẻ đẹp của khu vườn.
• Ở ví dụ thứ hai, 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 đó, độ tươi tốt của các cây lần lượt là ~[11,8,9]~ và vẻ đẹp của khu vườn là ~8~.
• Ở ví dụ thứ ba, ta sẽ tưới cả ~10~ lít nước vào cây thứ hai. Khi đó, độ tươi tốt của các cây lần lượt là ~[100, 30]~ và vẻ đẹp của khu vườn là ~30~.

Chấm điểm

• Subtask 1 (30% số test): ~n, L ≤ 1000~
• Subtask 2 (30% số test): ~L ≤ 10^5~
• Subtask 3 (40% số test): Không có ràng buộc gì thêm

Nguồn: Free Contest