FJ bắt đầu kinh doanh đồ lưu niệm, mua bán các món nhỏ như đồ trang trí cây thông Giáng sinh hình bò. Ông biết sẽ bán được mọi món nhập từ danh mục $N$ ($1 \le N \le 100$) loại đồ lưu niệm bò khác nhau và có thể mua mỗi loại bao nhiêu tùy thích. Chỉ có $M$ ($1 \le M \le 100,000$) tiền để đầu tư, nhưng ông muốn tối đa hóa lợi nhuận (định nghĩa hơi khác thường) vào cuối năm kinh doanh đầu tiên.

Món loại $i$ có giá mua $C_i$ ($1 \le C_i \le 100,000$), và mỗi món bán được đem lại doanh thu $R_i$ ($1 \le R_i \le 100,000$) (lợi nhuận $R_i-C_i$). FJ có thể phối hợp các loại bán ra tùy ý. Không cần tiêu hết tiền khi mua.

Lợi nhuận tổng cộng lớn nhất ($profit = initial\_cash - all\_costs + all\_sales$) cuối năm đầu là bao nhiêu? Bảo đảm số này nhỏ hơn $1,000,000,000$.

Xét chỉ $3$ loại đồ và số tiền ban đầu $M=17$. Chi phí và doanh thu của mỗi loại như sau:

             Đồ lưu niệm     Chi phí     Doanh thu
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

FJ nên mua $5$ món loại $3$ với $15$ tiền và thêm $1$ món loại $1$ với $2$ tiền, tổng cộng $17$. Lợi nhuận là $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$. Với cấu trúc chi phí và doanh thu này, ông không thể làm tốt hơn.

Lưu ý: ca kiểm thử thứ hai khó, nhưng đáp án của chúng tôi đúng.

Dữ liệu vào

• Dòng 1: hai số nguyên cách nhau bởi dấu cách: $N$ và $M$.

• Các dòng $2..N+1$: dòng $i+1$ chứa hai số nguyên cách nhau bởi dấu cách: $C_i$ và $R_i$.

Dữ liệu ra

• Dòng 1: lợi nhuận lớn nhất FJ có thể tạo ra với chi phí và doanh thu đã cho.

Ví dụ

Dữ liệu vào 1

3 17
2 4
5 6
3 7

Dữ liệu ra 1

22

Nguồn bài toán: bài toán truyền thống, 2009.