Cuộn giấy nhân đôi
Points
17
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$.
Community Discussion