Bessie muốn xem bộ phim Bovine Genomics: The Documentary nhưng mà hổng có mún đi một mình. Hổng may, mấy bẹn thân cũng hổng có hứng đi với Bessie! Vì vậy, Bessie cần phải hối lộ xíu để những người bạn này đi xem phim cùng. Ả có \(2\) cách để hối lộ: đồng tiền mooney hoặc kem ốc quế.

Bessie có \(N\) \((1 \le N \le 2000)\) người bạn. Tuy nhiên, không phải người bạn nào cũng như nhau! Người bạn \(i\) có độ nổi tiếng là \(P_i\) \((1 \le P_i \le 2000)\), và Bessie muốn cực đại hoá tổng độ nổi tiếng của những người bạn đi cùng ả ta đến rạp phim. Người bạn \(i\) sẵn sàng đi cùng với Bessie nếu như ả đưa cho \(C_i\) \((1 \le C_i \le 2000)\) đồng mooney và người bạn này sẽ giảm giá cho Bessie đi \(1\) đồng mooney nếu ả đưa cho \(X_i\) \((1 \le X_i \le 2000)\) cây kem ốc quế. Bessie có thể được giảm giá bao nhiêu tuỳ thích miễn là số đồng mooney được giảm không vượt quá số tiền mà Bessie cần đưa cho người bạn này.

Bessie có \(A\) đồng mooney và \(B\) cây kem trong ví \((0 \le A, B \le 2000)\). Hãy giúp cô ấy tìm ra tổng độ nổi tiếng lớn nhất có thể nếu cô ấy sử dụng mooney và kem một cách tối ưu.

Input

• Dòng \(1\) chưa ba số nguyên \(N, A, B\).
• Trong \(N\) dòng tiếp theo, mỗi dòng thứ \(i\) là ba số nguyên \(P_i, C_i, X_i\).

Output

• Tổng độ nổi tiếng lớn nhất.

Scoring

• Subtask \(1\): \(N \le 5, C_i = 1\).
• Subtask \(2\): \(B = 0\).
• Subtask \(3\): \(N, A, B, P_i, C_i, X_i \le 50\).
• Subtask \(4\): $\(N, A, B, P_i, C_i, X_i \le 200\).
• Subtask \(5\): Không có thêm ràng buộc.

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

15