Беси хочет посмотреть 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\)).
Помогите ей определить максимальную сумму популярностей, которую она может
добиться, если потратит mooney и мороженое оптмально.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Строка \(1\) содержит три числа \(N\), \(A\), \(B\), представляющих количества друзей,
mooney и мороженых, которые есть у Беси соответственно.
Каждая из последующих \(N\) строк содержит три числа \(P_i\), \(C_i\), \(X_i\),
представляющих популярность (\(P_i\)), mooney, за которые он согласится пойти,
количество мороженых для скидки в \(1\) mooney для друга \(i\) (\(X_i\)).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите максимальную сумму популярностей друзей Беси, в предположении
что она оптимально потратит moonie и мороженые.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 10 8
5 5 4
6 7 3
10 6 3
|
15
|