Trong cửa hàng quà lưu niệm gần trường có \(N\) món quà được đánh số thứ
tự từ \(1\) tới \(N\). Món quà thứ \(i\) \((i = 1 \dots N)\) có khối lượng là
\(x_i\) (gram) và giá bán là \(y_i\) (đồng). Ngoài ra cửa hàng còn đưa
ra chương trình khuyến mãi là với món quà thứ \(i\), cứ mỗi \(z_i\)
voucher thì được giảm giá bán món quà đó đi \(1\) đồng (voucher chỉ
có thể giúp giảm giá bán chứ không quy đổi được ra tiền). Lam đi vào cửa
hàng với số tiền là \(a\) đồng và số voucher là \(b\) voucher.

Yêu cầu: Bạn hãy giúp Lam xác định phương án sử dụng tiền và
voucher sao cho tổng khối lượng (gram) của các món quà mua được là
lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N, a, b\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) \((i = 1 \dots N)\) chứa ba số nguyên dương \(x_i, y_i, z_i\) \((x_i, y_i, z_i \le 2000)\).

Dữ liệu ra

Tổng khối lượng (gram) lớn nhất của các món quà mua được.

Phân nhóm

Ví dụ

3 10 0
7 3 7
6 7 8
9 1 6

16

3 8 10
5 5 4
6 7 3
10 6 3

15