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.

Input

• 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)~.

Output

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

Scoring

Sample Input 1

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

Sample Output 1

16

Sample Input 2

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

Sample Output 2

15

Notes

• Test 1: Phương án mua để được tổng khối lượng các món quà lớn nhất: Mua món quà thứ nhất sử dụng ~3~ đồng, mua món quà thứ ba sử dụng ~1~ đồng, khi đó tổng khối lượng các món quà mua được là ~16\ gram~.

• Test 2: Phương án mua để được tổng khối lượng các món quà lớn nhất: Mua món quà thứ ba sử dụng ~3~ đồng và ~9\ voucher~, mua món quà thứ nhất sử dụng ~5~ đồng, khi đó tổng khối lượng các món quà mua được là ~15\ gram~.