Mô tả và yêu cầu

Bài toán cái túi
Cho 𝑛 vật được đánh số thứ tự từ 1 đến 𝑛, vật thứ 𝑖 có khối lượng 𝑚𝑖 và giá trị là 𝑣𝑖. Bạn
có 𝑘 cái túi được đánh thứ tự từ 1 đến 𝑘, cái túi thứ 𝑖 có có thể chứa vật có khối lượng tối
đa là 𝑤𝑖. Bạn muốn tìm cách đặt các vật vào các túi sao cho mỗi túi chỉ chứa tối đa một vật
và tổng giá trị các vật trong các túi là lớn nhất có thể.
Yêu cầu: Hãy lập trình xác định giá trị lớn nhất tìm được.
Dữ liệu vào: cho trong file văn bản caitui.inp có cấu trúc như sau:
 Dòng đầu ghi hai số nguyên dương 𝑛 và 𝑘.
 𝑛 dòng tiếp theo, dòng thứ 𝑖 trong 𝑛 dòng này ghi hai số nguyên dương 𝑚𝑖 và 𝑣𝑖
(𝑚𝑖, 𝑣𝑖 ≤ 106).
 𝑘 dòng tiếp theo, dòng thứ 𝑖 trong 𝑘 dòng này ghi một số nguyên dương
𝑤𝑖 (𝑤𝑖 ≤ 109).
Kết quả: ghi ra file văn bản caitui.out chỉ một số là kết quả tìm được.

Ví dụ

caitui.inp                 caitui.out
                             3 2                        17
                             1 7
                             5 9
                             4 10
                             2
                             10
Giới hạn:
       50% số test tương ứng với 50% số điểm có 𝑛,             𝑘  ≤  5000.
       50% số test tương ứng với 50% số điểm có 𝑛,             𝑘  ≤  3 ×  105.