#1547. CLOUD - Điện toán đám mây

Hải Dương đang có ý định thành lập công ty CloudComp chuyên cung cấp dịch vụ tính toán điện toán đám mây. Việc đầu tiên Hải Dương cần làm là đi tìm hiểu để mua máy tính cung cấp dịch vụ. Qua tìm hiểu, Hải Dương nhận được danh sách máy tính (đánh số từ đến ), máy tính thứ được đặc trưng bởi bộ số nguyên dương tương ứng là số lõi, tần số xung nhịp và giá bán.

Hải Dương cũng đã nhận được đơn hàng cung cấp dịnh vụ điện toán đám mây (đánh số từ đến ). Đơn hàng thứ yêu cầu cung cấp dịch vụ với bộ số nguyên dương tương ứng là số lõi, tần số xung nhịp tối thiểu của các lõi và giá thuê dịch vụ. Nếu đơn hàng được chấp nhận thì CloudComp cần cung cấp cho khách hàng lõi (có thể lấy tử các máy tính khác nhau, những lõi này chưa cung cấp cho bất cứ một đơn hàng nào trước đó), tần số xung nhịp tối thiểu của các lõi là và sẽ nhận được khoản tiền là .

Yêu cầu: Bạn hãy giúp Hải Dương tính toán chọn mua máy tính cũng như chọn các đơn hàng để cung cấp dịch vụ sao cho thu được lợi nhận lớn nhất (lợi nhuận chênh lệch giữa số tiền thu được từ việc cung cấp dịch vụ và chi phí bỏ ra để mua các máy tính).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương là số máy tính có thể mua;
• dòng tiếp theo, dòng thứ chứa ba số nguyên dương ;
• Dòng tiếp theo chứa số nguyên dương là số đơn hàng yêu cầu cung cấp dịch vụ;
• dòng tiếp theo, dòng thứ chứa ba số nguyên ;

Các số trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

• Một số nguyên duy nhất là lợi nhuận lớn nhất thu được.

Ví dụ:

Dữ liệu vào:

4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550

Dữ liệu ra:

350

Giải thích:

• Mua máy tính số và số với tổng số tiền là ;
• Cung cấp dịch vụ cho đơn hàng số và số thu được ;

Lợi nhuận thu được là (tối đa)

Giới hạn:

Trong tất cả các test có: ;

• Subtask số điểm có ;
• Subtask số điểm khác có ;
• Subtask số điểm khác có ;
• Subtask số điểm khác có ;
• Subtask số điểm khác có ;
• Subtask số điểm còn lại không có ràng buộc bổ sung.