Cuộn giấy nhân đôi

Buổi 24 — Mock Contest Phase 1
Points
17
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Bạn có $N$ bảo vật, bảo vật thứ $i$ có trọng lượng $w_i$ và giá trị $v_i$. Chiếc túi của bạn chỉ chịu được tổng trọng lượng tối đa $W$.

Ngoài ra, bạn sở hữu một cuộn giấy phép thuật: bạn có thể dùng nó lên tối đa một bảo vật đã chọn để nhân đôi giá trị của bảo vật đó (trọng lượng vẫn giữ nguyên là $w_i$).

Tìm tổng giá trị lớn nhất có thể mang theo.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, W$ ($1 \le N \le 500$, $0 \le W \le 5000$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i, v_i$ ($1 \le w_i \le 5000$, $1 \le v_i \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng giá trị lớn nhất.
Ví dụ
Input Output
3 5
2 3
3 4
4 5
11
2 3
4 10
5 20
0
Giới hạn
  • $1 \le N \le 500$, $0 \le W \le 5000$.
  • $1 \le w_i \le 5000$, $1 \le v_i \le 10^9$.
Draft saved