Elearning CodePath – CTP Online Judge

Phân phối Quà Giáng Sinh

GEN013

🟢 Easy #Greedy

### 📌 Thông tin chung

Ông già Noel có tổng cộng $A+B+C$ túi quà để lấp đầy, trong đó:
* $A$ túi dành riêng cho miền núi (chỉ chứa quà loại N hoặc C).
* $B$ túi dành riêng cho miền đồng bằng (chỉ chứa quà loại B hoặc C).
* $C$ túi quà đặc biệt (có thể dùng cho cả núi và đồng bằng).

Có $M$ món quà có sẵn. Mỗi món quà thứ $i$ được mô tả bởi giá sản xuất $v_i$ và loại:
* 'N': Dành riêng cho miền núi.
* 'B': Dành riêng cho miền đồng bằng.
* (Giả định rằng các món quà không được gán loại 'C', mà 'C' chỉ là loại túi đặc biệt có thể chứa cả 'N' và 'B'. 
* **Dựa trên ví dụ, ta giả định mỗi món quà chỉ lấp đầy một túi quà**).

**Mục tiêu:**
1. **Tối đa hóa** số lượng túi quà được lấp đầy (mỗi túi chứa một món quà).
2. Trong số các phương án tối đa hóa số túi, **tối thiểu hóa** tổng chi phí sản xuất của các món quà được chọn.

Tổng số túi tối đa có thể lấp đầy là $\min(M, A+B+C)$.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `BAI4.INP`:

* Dòng 1: Ba số nguyên $A, B, C$ (số lượng túi miền núi, đồng bằng, đặc biệt).
* Dòng 2: Số nguyên $M$ (số món quà có sẵn).
* $M$ dòng tiếp theo: Mỗi dòng mô tả món quà thứ $i$ với giá sản xuất $v_i$ và loại ('N' hoặc 'B').

Giới hạn (Không được cho rõ, nhưng từ Subtask ta suy luận):
* $A, B, C$ là các số nguyên dương.
* $M$ có thể lên đến vài nghìn.
* $v_i$ là giá sản xuất.

---
### 📤 Định dạng Đầu ra

Ghi ra file `BAI4.OUT` hai số nguyên trên một dòng:

* Số túi quà được lấp đầy (số món quà được sử dụng).
* Tổng chi phí sản xuất nhỏ nhất.

---
### ✨ Ví dụ

| Dữ liệu | Kết quả | 
| :--- | :--- | 
| `2 1 1` `4` `5 N` `6 B` `3 B` `7 B` | `3 14` |

Giải thích:
Tối đa lấp được 3 túi. $A=2, B=1, C=1$. 
Món quà $N$ (giá 5) được dùng cho túi $A$. 
Món quà $B$ giá 3 và 6, ta chọn 2 món $B$ rẻ nhất (giá 3 và 6) cho túi $B$ và $C$. 
Tổng chi phí: $5+3+6 = 14$. 
---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $A=0, B=0$ | $15\%$ |
| 2 | $C=0$ | $15\%$ |
| 3 | $M \le 20$ | $20\%$ |
| 4 | $M \le 1000$ | $30\%$ |
| 5 | Không có ràng buộc bổ sung (Giả định $M$ lớn) | $20\%$ |

---

✅ Đã AC: 2 / 8 submissions