Problem
Bạn là người quản lý và lên kế hoạch làm việc cho tháng tới. Mỗi tháng được chia thành T đơn vị thời gian bằng nhau. Tổng cộng có n nhiệm vụ cần được thực hiện. Tuy nhiên, bạn hiểu rằng có thể không hoàn thành tất cả các nhiệm vụ trong một tháng và bạn muốn lập một kế hoạch tối ưu bằng cách chọn một số nhiệm vụ trong số đó để hoàn thành.
Đối với mỗi nhiệm vụ, chúng tôi biết thời gian ti cần bỏ ra để hoàn thành nhiệm vụ đó, cũng như lợi nhuận pi< /sub> mà nhiệm vụ hoàn thành sẽ mang lại lợi nhuận cho công ty. Bạn muốn lên kế hoạch cho một số nhiệm vụ sao cho:
- Tổng thời gian dành cho các nhiệm vụ có trong kế hoạch không vượt quá
T.
- Tổng lợi nhuận từ những nhiệm vụ này là tối đa.
Lập một kế hoạch có các thuộc tính được mô tả ở trên và xác định lợi nhuận thu được từ việc thực hiện kế hoạch này.
Xin lưu ý rằng kế hoạch duy nhất phù hợp với các điều kiện có thể không chứa bất kỳ nhiệm vụ nào.
Dữ liệu nhập
Dòng đầu tiên chứa các số tự nhiên T (1 ≤ T ≤ 100 000) và n (1 ≤ n &le ; 10) - số đơn vị thời gian mỗi tháng và số nhiệm vụ.
Các dòng n sau đây chứa hai số tự nhiên mỗi dòng ti và pi (1 <= ti, pi <= 100 000) - thời gian dành cho hoàn thành nhiệm vụ thứ ivà lợi nhuận có thể nhận được khi hoàn thành nhiệm vụ đó.
Dữ liệu nhà xuất bản
In một số duy nhất — lợi nhuận tối đa có thể đạt được bằng cách vạch ra một kế hoạch đáp ứng các điều kiện được viết ở trên.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |