Descripción

Como ávido coleccionista de tarjetas de Yu-Gi-Oh! cada que cae algún dinero en tus manos lo gastas en conseguir las tarjetas mas poderosas para mejorar tu nivel de juego, y aunque gastas todo tu dinero de esta manera tan irrazonable, deseas por supuesto gastarlo de la manera mas razonable (valga la incongruencia). Por lo tanto te interesa obtener las mejores tarjetas posibles por tu dinero.

Para lograrlo has catalogado todas las tarjetas que te interesan asignándoles un puntaje de 0 a 100 dependiendo de cuanto te interesan.

Cabe mencionar que únicamente te interesa tener una copia de cada tarjeta, por lo que todas las tarjetas de tu lista son distintas y en caso de comprarlas compraras únicamente una copia de cada una.

Por lo tanto deberás escribir un programa que dada, la cantidad $D$ de dinero con que cuentas, el número $N$ de tarjetas diferentes disponibles, el precio $P_i$ de cada una de las tarjetas, y el puntaje $U_i$ que tu le asignas a cada una de las tarjetas, te devuelva cual es el puntaje máximo que puedes obtener en tarjetas con tu dinero.

Entrada

Tu programa deberá leer del teclado los siguientes datos, en la primera línea dos números enteros separados por un espacio que corresponden a $D$ y $N$ respectivamente. En las siguientes $N$ líneas habrá en cada línea dos números separados por un espacio indicando el precio $P$ y el puntaje $U$ de esa tarjeta.

Salida

Tu programa deberá escribir en la pantalla un único número que indica el puntaje máximo en tarjetas que puedas obtener con tu dinero.

Ejemplo

15 4
2 10
9 18
6 12
4 10

38

Límites:

• 1 <= $D$ <= 10000
• 1 <= $N$ <= 500
• 1 <= $P_i$ <= 100
• 0 <= $U_i$ <= 100.