Bessie quiere ver Genomics Bovinos: El Documental, pero no quiere ir sola. Desafortunadamente, a sus amigas no les agrada ir con ella. Por lo tanto, Bessie necesita sobornar a sus amigas para acompañarla al teatro. Ella tiene dos herramientas en su arsenal de soborno: moonedas y conos de helado.

Bessie tiene ~N~ amigas. Sin embargo, no todas las amigas son creadas iguales. La amiga ~i~ tiene un puntaje de popularidad de ~P_i~, y Bessie quiere maximizar la suma de los puntajes de popularidad de las amigas que la acompañen. La amiga ~i~ está dispuesta a acompañar a Bessie si ella le da ~C_i~ moonedas. Ellas también le ofrecen un descuento de ~1~ mooneda si ella les da ~X_i~ conos de helado. Bessie puede obtener tantos descuentos de números enteros de una amiga, en tanto que los descuentos no causen que la amiga le de sus moonedas.

Bessie tiene ~A~ moonedas y ~B~ conos de helado a su disposición. Ayúdela a determinar la suma máxima de puntajes de popularidad que ella puede conseguir si ella gasta sus moonedas y helados de manera óptima.

Entrada

La línea ~1~ contiene tres números ~N, A~, y ~B~, representando el número de amigas, la cantidad de moonedas, y el número de conos de helado que Bessie tiene respectivamente.

Cada una de las siguientes ~N~ líneas contiene tres números, ~P_i, C_i,~ y ~X_i~, representando popularidad (~P_i~), las moonedas necesarias para sobornar a la amiga ~i~ para acompañar a Bessie (~C_i~), y los conos necesarios para recibir un descuento de ~1~ mooneda de la amiga ~i~ (~X_i~).

Salida

Imprima la suma máxima de puntajes de popularidad de las amigas acompañando a Bessie, asumiendo que ella gasta sus moonedas y conos de helado óptimamente.

Restricciones

• ~1 \leq N \leq 2000~
• ~1 \leq P_i \leq 2000~
• ~1 \leq C_i \leq 2000~
• ~1 \leq X_i \leq 2000~
• ~0 \leq A,B \leq 2000~

Ejemplo de Entrada

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

Ejemplo de Salida

15

Bessie puede dar 4 moonedas y 4 conos de helado a la vaca 1, y 6 moonedas y 3 conos de helado a la vaca 3, para conseguir que las vacas 1 y 3 la acompañen con una popularidad de ~5+10=15~.

Calificaciones

Casos	Restricciones adicionales
2-4	~N \leq 5~ y ~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	Sin más restricciones

USACO 2022 December Contest, Gold Problem 1. Bribing Friends.