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à muosn 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 \leq n \leq 1000)\) và \(k\ (1 \leq k \leq 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} \leq 1024)\), \(b_{i}\ (1 < b_{i} \leq 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 \leq i \leq 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ụ:

Có 5 loại ảnh, dung lượng thẻ nhps 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 \leq n \leq 500;k \leq 2;a_{i} \leq 1024,\ b_{i} \leq 32000\);

+ 50% test ứng với \(2 \leq n \leq 1000;k \leq 4;a_{i} \leq 1024,\ b_{i} \leq 10^{9}\);