Elearning CodePath – CTP Online Judge

Chọn Phương Án Theo Nhóm

GROUPPACK

## Đề bài

Có `g` nhóm phương án. Nhóm thứ `i` có `mi` phương án.

Mỗi phương án có chi phí `w` và giá trị `v`. Từ mỗi nhóm, bạn được chọn tối đa một phương án, cũng có thể không chọn phương án nào trong nhóm đó.

Tổng chi phí các phương án được chọn không được vượt quá `W`.

Hãy tìm tổng giá trị lớn nhất.

## Dữ liệu vào

Dòng 1 chứa hai số nguyên `g, W`.

Với mỗi nhóm:

- Một dòng chứa số nguyên `mi`.
- `mi` dòng tiếp theo, mỗi dòng chứa hai số nguyên `w, v` của một phương án.

## Dữ liệu ra

In ra tổng giá trị lớn nhất.

## Giới hạn

- `1 ≤ g ≤ 100`
- `1 ≤ W ≤ 200000`
- `1 ≤ mi ≤ 20`
- `1 ≤ w ≤ W`
- `1 ≤ v ≤ 10^9`

## Phân loại subtask

| Subtask | Ràng buộc | Điểm |
| --- | --- | --- |
| 1 | `g ≤ 8`, `W ≤ 500`, `mi ≤ 5` | 30% |
| 2 | `g ≤ 50`, `W ≤ 20000`, `mi ≤ 10` | 30% |
| 3 | Không có ràng buộc bổ sung | 40% |

## Ví dụ

### Input
```text
2 7
2
3 4
4 7
2
3 5
2 4
```

### Output
```text
12
```

### Giải thích

Chọn phương án `4 7` ở nhóm 1 và phương án `3 5` ở nhóm 2. Tổng chi phí `7`, tổng giá trị `12`.

✅ Đã AC: 0 / 0 submissions