Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Có $G$ nhóm đồ vật, nhóm thứ $i$ gồm $M_i$ đồ vật, mỗi đồ vật có trọng lượng $w$ và giá trị $v$. Bạn có một chiếc ba lô sức chứa $W$. Từ mỗi nhóm, bạn chỉ được chọn tối đa một đồ vật.

Hãy tìm tổng giá trị lớn nhất có thể mang theo sao cho tổng trọng lượng không vượt quá $W$.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $G, W$ ($1 \le G \le 100$, $1 \le W \le 10^4$).
  • Tiếp theo là mô tả $G$ nhóm. Mỗi nhóm bắt đầu bằng một dòng chứa số nguyên $M_i$ ($1 \le M_i \le 50$), theo sau bởi $M_i$ dòng, mỗi dòng chứa hai số nguyên $w, v$ ($1 \le w \le 10^4$, $1 \le v \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
2 5<br>2<br>2 4<br>3 5<br>2<br>3 6<br>4 7 10
Giới hạn
  • $1 \le G \le 100$, $\sum M_i \le 1000$
  • $1 \le W \le 10^4$
Draft saved