Trong cửa hàng có \(n\) món đồ được đánh số thứ tự từ \(1\) tới \(n\). Món đồ thứ \(i\ (1 \leq i \leq n)\) có khối lượng là \(x_{i}\) kg 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 đồ thứ \(i\), cứ mỗi \(z_{i}\) voucher thì được giảm giá bán món đồ thứ \(i\) đi 1 đồng (voucher chỉ có thể giúp giảm giá bán chứ không quy đổi được ra tiền). An đi vào cửa hàng với số tiền là \(a\) đồng và số voucher là \(b\) voucher. Bạn hãy giúp An xác định phương án sử dụng tiền và voucher sao cho tổng khối lượng của các món đồ mua được là lớn nhất.

Dữ liệu vào:

+ Dòng 1 chứa số nguyên \(n,\ a,\ b\) lần lượt là số món đồ trong cửa hàng, số tiền và số voucher;

+ \(n\) dòng tiếp theo, dòng thứ \(i\ (1 \leq i \leq n)\) trong \(n\) dòng này chứa 3 số nguyên dương \(x_{i},\ y_{i},\ z_{i}\ \)lần lượt là khối lượng, giá bán và số voucher để giảm giá đi 1 đồng với món đồ thứ \(i\).

Kết quả:

+ Đưa ra một số nguyên duy nhất là tổng khối lượng (kg) tối đa của các món đồ mua được.

Ví dụ:

Giải thích:

Một phương án mua để được tổng khối lượng các món đồ lớn nhất: mua món thứ 3 sử dụng 3 đồng và 9 voucher, mua món thứ nhất sử dụng 5 đồng, khi đó tổng khối lượng nhận được là 15.

Ràng buộc:

• Ràng buộc 1: ứng với 20% số điểm có \(1 \leq n \leq 2000;0 \leq a \leq 2000;b = 0;1 \leq x_{i},\ y_{i},z_{i} \leq 2000\);

• Ràng buộc 2: ứng với 20% số điểm có \(1 \leq n \leq 5;0 \leq a,b \leq 50;\ 1 \leq x_{i},\ y_{i},z_{i} \leq 50\);

• Ràng buộc 3: ứng với 30% số điểm có \(1 \leq n \leq 50;0 \leq a,b \leq 50;\ 1 \leq x_{i},\ y_{i},z_{i} \leq 50\);

• Ràng buộc 4: ứng với 30% số điểm có \(1 \leq n \leq 200;0 \leq a,b \leq 200;\ 1 \leq x_{i},\ y_{i},z_{i} \leq 200\).