Бесі хоче подивитися Bovine Genomics: The Documentary, але вона не хоче йти сама. На жаль, її друзі не дуже хочуть іти з нею. Їй потрібно чимось їх залучити. Вона має два інструменти: mooney та морозиво.

У Бесі \(N\) (\(1 \le N \le 2000\)) друзів. Але вони різні! Друг \(i\) має рахунок популярності \(P_i\) (\(1 \le P_i \le 2000\)), і Бесі хоче максимізувати суму популярності друзів, які підуть із нею. Друг \(i\) піде з нею тільки якщо вона дасть йому \(C_i\) (\(1 \le C_i \le 2000\)) "moonies". Друг \(i\) також може зробити знижку в \(1\) "mooney", якщо вона дасть йому \(X_i\) (\(1 \le X_i \le 2000\)) морозива. Бесі може отримати скільки завгодно знижок.

У Бесі є \(A\) moonies і \(B\) морозива (\(0 \le A, B \le 2000\)). Допоможіть їй визначити максимальну суму популярності, якої вона може домогтися, якщо витратить moonies і морозиво оптимально.

Формат вхідних даних

Рядок \(1\) містить три числа \(N\), \(A\), \(B\), що представляють кількості друзів, mooney і морозиво, які є у Бесі відповідно.

Кожен з наступних \(N\) рядків містить три числа \(P_i\), \(C_i\), \(X_i\), популярних (\(P_i\)), mooney, за які він погодиться піти, кількість морозива для знижки \(1\) mooney для друга \(i\) (\(X_i\)).

Формат вихідних даних

Виведіть максимальну суму популярностей друзів Бесі, в припущенні що вона оптимально витратить moonie та морозиво.

Приклад вхідних даних

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

Приклад вихідних даних

15

Бесі може дати \(4\) moonies і \(4\) морозива корові \(1\), і \(6\) moonies і \(3\) морозива корові \(3\), в результаті корови \(1\) і \(3\) підуть з нею, та сумарна популярність \(5 + 10 = 15\).

ОЦІНЮВАННЯ:

• У тестах 2-4 \(N \leq 5\) and \(C_i = 1\)
• У тестах 5-7 \(B = 0\)
• У тестах 8-10 \(N, A, B, P_i, C_i, X_i \leq 50\)
• У тестах 11-15 \(N, A, B, P_i, C_i, X_i \leq 200\)
• У тестах 16-20 немає додаткових обмежень