Bốn năm cấp hai là khoảng thời gian ghi dấu nhiều kỉ niệm nhất của tuổi học trò và nhưng tình bạn đẹp cũng thường từ đây mà xuất hiện. Trong 4 năm qua, Hoàng và các bạn cùng lớp 9A của mình đã có rất nhiều hình ảnh đáng nhớ! Mỗi loại bức ảnh đều có dung lượng và tính thẩm mỹ nhất định. Để lưu trữ lại những hình ảnh đẹp, Hoàng quyết định mua một chiếc thẻ nhớ ngoài dung lượng ~ K ~ (Gigabyte – BG) để lưu chúng.

Hoàng thấy việc này thật thú vị và muốn tạo một hoạt động vui nhộn cùng các bạn với nội dung như sau:

Cho biết thông tin về số lượng các loại bức ảnh; mỗi loại sẽ có dung lượng và tính thẩm mỹ của loại đó.

Câu hỏi của Hoàng là: “Hãy chọn các bức ảnh của từng loại để lưu vào thẻ nhớ mà mình đã mua sao cho tổng tính thẩm mỹ thu được là lớn nhất”. Biết rằng một loại ảnh có thể không được chọn hoặc chọn với số lượng không hạn chế.

Yêu cầu: Cho biết tổng giá trị lớn nhất của tính thẩm mỹ thu được khi trả lời đúng câu hỏi của Hoàng là bao nhiêu?

Dữ liệu vào:

• Dòng thứ nhất chứa hai số ~ n (2≤n≤1000) ~ và ~ k (1≤k≤4) ~. Trong đó ~ n ~ là số lượng các loại ảnh của Hoàng được đánh số thứ tự từ 1 đến ~ n ~, ~ k ~ là dung lượng của thẻ nhớ Hoàng đã mua (tính bằng đơn vị GB);
• Trong ~ n ~ dòng tiếp theo, dòng thứ ~ i ~ chứa 2 số nguyên dương ~ a_i~ ~(1<a_i≤1024) ~, ~ b_i~ ~(1<b_i≤10^9) ~, trong đó ~ a_i ~ là dung lượng của bức ảnh loại thứ ~ i ~ theo đơn vị Megabyte (MB) và ~ b_i ~ là giá trị tính thẩm mỹ của bức ảnh loại thứ ~ i (1≤i≤n) ~.

Ghi chú: ~1GB= 1024MB~

Kết quả:

• Ghi một số nguyên duy nhất là kết quả bài toán

Ví dụ:

Input

5 1
800 1000
700 690
200 30
300 40
100 50 

Output

1100 

Có 5 loại ảnh, dung lượng thẻ nhớ của Hoàng là ~1GB~ ~(1024MB)~, nên sẽ chọn 1 ảnh loại 1 và 2 ảnh lại 5 để lưu giữ, có tổng giá trị thẩm mỹ ~1100~ là lớn nhất

Ràng buộc:

• 50% test ứng với ~ 2≤n≤500;k≤2;a_i≤1024, b_i≤32000 ~;
• 50% test ứng với ~ 2≤n≤1000;k≤4;a_i≤1024, b_i≤10^9 ~;