Ông X đang lên kế hoạch trồng cây trong khu vườn của mình. Có \(𝑛\) loại cây mà ông cân nhắc muốn trồng. Cụ thể, nếu ông mua \(𝑠\) cây loại thứ \(𝑖\) thì ông cần bỏ ra \(𝑠 × 𝑐_𝑖\) đồng và hiệu quả kinh tế của \(𝑠\) cây loại đó đem lại là \(𝑣_𝑖 + (𝑣_𝑖 − 𝑤_𝑖) + ⋯ + (𝑣_𝑖 − (𝑠 − 1) × 𝑤_𝑖) \) Ông \(X\) dự định sẽ bỏ ra tất cả \(𝑇\) đồng và muốn tìm phương án mua để tổng hiệu quả kinh tế là lớn nhất.

Yêu cầu: Cho \(𝑛\) loại cây, cây thứ \(𝑖\) (\(𝑖 = 1,2, … , 𝑛\)) có các thông tin là \(𝑐_𝑖, 𝑣_𝑖, 𝑤_𝑖\) và \(𝑚\) câu hỏi \(𝑇_1, 𝑇_2, … , 𝑇_𝑚\). Với mỗi câu hỏi \(𝑇_𝑘 (𝑘 = 1,2, … , 𝑚)\), hãy tìm phương án giúp ông\( X\) dùng không quá \(𝑇_𝑘\) đồng để mua những loại cây nào và số lượng tương ứng là bao nhiêu để tổng hiệu quả kinh tế là lớn nhất.

Dữ liệu:

• Dòng đầu chứa hai số nguyên dương \(𝑛, 𝑚 (𝑚 ≤ 10)\);

• Tiếp theo là \(𝑛\) dòng, mỗi dòng chứa ba số nguyên dương \(𝑐_𝑖, 𝑣_𝑖, 𝑤_𝑖 (𝑐_𝑖, 𝑣_𝑖, 𝑤_𝑖 ≤ 1000)\);

• Cuối cùng là một dòng chứa \(𝑚\) số nguyên dương \(𝑇_1, 𝑇_2, … , 𝑇_𝑚 (𝑇_𝑘 ≤ 1000)\).

Kết quả:

Ghi gồm một dòng chứa \(𝑚\) số nguyên là tổng hiệu quả kinh tế lớn nhất mà ông \(X\) có thể đạt được tương ứng với \(𝑚\) câu hỏi trong dữ liệu vào.

Sample Input

3 1 
5 10 5 
4 7 2 
1 1 1 
10

Sample Output

18

Sample Input

3 2 
5 10 1 
4 7 2 
1 1 1 
10 15

Sample Output

19 27

Ràng buộc:

- Có 30% số lượng test thỏa mãn điều kiện: 𝑛 = 3; 
- Có 30% số lượng test khác thỏa mãn điều kiện: 𝑛 ≤ 100; 
- Có 40% số lượng test còn lại thỏa mãn điều kiện: 𝑛 ≤ 10^5.