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\).

Dữ liệu ra:

• Đư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.

Input 1

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

Output 1

15

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 \le n \le 2000; 0 \le a \le 2000; b = 0; 1 \le x_i, y_i, z_i \le 2000\);
• Ràng buộc 2: ứng với 20% số điểm có \(1 \le n \le 5; 0 \le a, b \le 50; 1 \le x_i, y_i, z_i \le 50\);
• Ràng buộc 3: ứng với 30% số điểm có \(1 \le n \le 50; 0 \le a, b \le 50; 1 \le x_i, y_i, z_i \le 50\);
• Ràng buộc 4: ứng với 30% số điểm có \(1 \le n \le 200; 0 \le a, b \le 200; 1 \le x_i, y_i, z_i \le 200\).