Bài 4 (3.0 điểm). Tuần lễ ca nhạc (MUSIC.*) Ở vương quốc Omega tươi đẹp, Quốc Vương tổ chức tuần lễ ca nhạc để kỷ niệm ngày quốc khánh. Đoàn ca nhạc trên toàn vương quốc được mời đến biểu diễn. Ban tổ chức nhận được n tiết mục văn

Để giải quyết bài toán này, chúng ta cần xác định cách tối ưu nhất để chọn các file video sao cho số lượng file video được lưu trữ vào hai USB là nhiều nhất, mà không vượt quá dung lượng của từng USB.

Dữ liệu đầu vào cho biết số lượng file video n và dung lượng tối đa W của từng USB, cũng như kích thước của từng file video.

### Các bước giải quyết:

1. Đọc dữ liệu: Đầu tiên, chúng ta sẽ đọc số lượng file video n và dung lượng W từ file MUSIC.INP, sau đó đọc kích thước của từng file video vào một danh sách.

2. Phân tích bài toán: Bài toán có thể được xem như một bài toán knapsack (balo) trong đó chúng ta cần tối đa hóa số lượng file video (các vật phẩm) có thể lưu trữ vào hai USB. Mỗi file video có thể được lưu trữ vào một USB, không thể lưu trữ vào cả hai USB. Tức là mỗi file video sẽ có kích thước là Ai.

3. Tối ưu hóa:
- Ta sẽ sử dụng một biến thể của thuật toán knapsack để tìm số lượng tối đa các file video mà có thể cất chứa trên một USB mà không vượt quá dung lượng W.
- Tạo một mảng dp để lưu trữ giá trị tối đa số lượng file video có thể được cất vào một USB với các dung lượng từ 0 đến W.
- Duyệt qua từng file video và cập nhật dp theo hướng từ lớn đến nhỏ để tránh bị tính gộp.

4. Xử lý cho hai USB: Sau khi tìm được số lượng tối đa file video cho một USB (nhiều nhất là V), ta cần xử lý cho cả hai USB. Cần lưu ý rằng có thể lấy file từ một USB này sang USB khác trong trường hợp không thể lấy đủ số lượng file vào một USB duy nhất, nên tối đa số lượng file cho cả hai USB sẽ là tổng số lượng file video tối đa mà hai USB có thể lưu trữ với dung lượng tổng cộng là 2W.

### Triển khai giải thuật:

```python
# Đọc dữ liệu từ file
with open('MUSIC.INP', 'r') as f:
n, W = map(int, f.readline().split())
A = list(map(int, f.readline().split()))

# Hàm tính số lượng file tối đa cho một USB
def max_files(W, A):
dp = [0] * (W + 1)
for size in A:
for j in range(W, size - 1, -1):
dp[j] = max(dp[j], dp[j - size] + 1)
return dp[W]

# Số lượng tối đa có thể lưu vào một USB
max_one_usb = max_files(W, A)

# Số lượng tối đa có thể lưu vào hai USB
max_two_usb = min(n, max_one_usb * 2)

# Ghi kết quả ra file
with open('MUSIC.OUT', 'w') as f:
f.write(str(max_two_usb))
```

### Giải thích:
- Tại mỗi bước, ta xác định xem có thể thêm file video nào vào USB hay không bằng cách kiểm tra kích thước file đó và cập nhật DP.
- Sau khi tính toán cho một USB, ta nhân đôi số lượng file tối đa cho hai USB (nhưng không vượt quá n).
- Kết quả cuối cùng được ghi vào file MUSIC.OUT.

Phương pháp này đảm bảo ta tìm ra giải pháp tối ưu cho bài toán trong thời gian hợp lý.