Elearning CodePath – CTP Online Judge

CHONDO

Hùng có n đồ dùng cần mang đi. Đồ dùng thứ i có trọng lượng là W_i và giá trị sử dụng là V_i.

Do hành lý xách tay vượt quá trọng lượng cho phép, Hùng phải chọn ra một số đồ dùng thật cần thiết để giữ lại trong hành lý xách tay, sao cho tổng trọng lượng của các đồ dùng được chọn không vượt quá m.

Hãy xác định phương án chọn đồ sao cho tổng giá trị sử dụng là lớn nhất.

Nếu có nhiều phương án cùng đạt tổng giá trị sử dụng lớn nhất, hãy chọn phương án có tổng trọng lượng nhỏ nhất.

Dữ liệu vào

| Thành phần | Mô tả |
|---|---|
| Dòng 1 | Hai số nguyên dương n và m |
| n dòng tiếp theo | Dòng thứ i chứa hai số nguyên dương W_i và V_i |

Ràng buộc đề xuất

| Thành phần | Giới hạn |
|---|---|
| n | $1 \le n \le 100$ |
| m | $1 \le m \le 10^5$ |
| $W_i $| $1 \le W_i \le m$ |
|$V_i$ | $1 \le V_i \le 10^9$ |

Kết quả ra

| Thành phần | Mô tả |
|---|---|
| Dòng 1 | Tổng giá trị sử dụng lớn nhất của các đồ dùng được chọn |
| Dòng 2 | Tổng trọng lượng của phương án được chọn |

Ví dụ

| CHONDO.INP | CHONDO.OUT |
|---|---|
| 3 10<br>3 2<br>2 6<br>7 4 | 10<br>9 |

Giải thích

Chọn đồ dùng thứ 2 và thứ 3. Khi đó tổng trọng lượng là:

$2 + 7 = 9$

và tổng giá trị sử dụng là:

$6 + 4 = 10$

Subtask

| Subtask | Ràng buộc | Tỷ lệ điểm |
|---|---|---|
| 1 | $n \le 20$ | 50% |
| 2 | Không có ràng buộc gì thêm | 50% |

✅ Đã AC: 0 / 3 submissions