Bài toán cái túi

Xem PDF
Tác giả:
kitsune
Dạng bài
Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(n\) món đồ được đánh chỉ số từ \(1\) đến \(n\), món đồ thứ \(i\) có trọng lượng \(w_{i}\) và giá trị \(v_{i}\). Hãy chọn một số món đồ sao cho tổng trọng lượng không vượt quá \(m\) và tổng giá trị là lớn nhất có thể.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 10^{5})\).
  • Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(w_{i}\) và \(v_{i}\) \((1 \leq w_{i}, v_{i} \leq 10)\).

Output

  • Một dòng duy nhất chứa một số nguyên là tổng giá trị lớn nhất tìm được.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(n, m \leq 10^{3}\).
  • Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
6 15
6 5
5 6
6 4
6 6
3 5
7 2
Output 
17

Bình luận