(trochoihn.*)

Trong một trò chơi huận luyện thú, mỗi người chơi sẽ sở hữu một con thú và sẽ huấn luyện để con thú của mình có điểm sức mạnh lớn nhất. Người chơi có \(m\) phút huấn luyện con thú của mình:

+ Có \(n\) kĩ năng người chơi có thể lựa chọn để huấn luyện cho con thú;

+ Mỗi phút huấn luyện kĩ năng thứ \(i\), con thú sẽ được tăng thêm \(e_{i}\) điểm sức mạnh (có thể huận luyện một kỹ năng nhiều lần);

+ Với kĩ năng thứ \(i\) mà con thú được huận luyện lần đầu, con thú sẽ được tăng thê \(s_{i}\) điểm sức mạnh.

Yêu cầu: Hãy lên phương án huấn luyện trong \(m\) phút để điểm sức mạnh của con thú là lớn nhất.

Dữ liệu vào:

+ Dòng dầu tiên chứa hai số nguyên dương \(n,\ m\ (1 \leq n \leq 10^{5};1 \leq m \leq 10^{9})\) là số lượng kĩ năng và thời gian huấn luyện cho thú;

+ \(n\) dòng sau, dòng thứ \(i\) chứa hai số nguyên dương \(s_{i},\ e_{i}(s_{i},\ e_{i} \leq 10^{6};1 \leq i \leq n)\) là điểm sức mạnh được tăng khi huấn luyện kĩ năng lần đầu và điểm sức mạnh của kĩ năng.

Kết quả:

+ Số điểm sức mạnh tối đa có thể đạt được.

Ví dụ:

Ràng buộc:

+ Có 40% số test ứng với 40% số điểm thỏa mãn: \(m = 2\);

+ Có 40% số test khác ứng với 40% số điểm thỏa mãn: \(m \leq 100\);

+ Có 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.