Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Un chofer maneja un taxi rutero que tiene capacidad para $N$ personas. Al llegar a una parada, como hay muchas personas, estas se encuentran dispuestas a pagarle una cantidad exagerada de dinero para viajar en su taxi. Se sabe que hay personas que andan en pareja, y no es posible que se vaya una de las dos y la otra se quede. Es necesario destacar que las personas que viajan en pareja ofrecen una cantidad de dinero por irse las dos, y solamente una de ellas le hace la oferta al chofer. Lo que se quiere es determinar cuál es la ganancia máxima que puede tener el chofer con las propuestas que le hacen.

Input

Línea 1 : La primera línea de la entrada contiene dos enteros $N$ y $M$ $(1 \le N, M \le 10^5)$, que representan la capacidad del taxi y la cantidad de ofertas que le hacen al chofer respectivamente.
Línea 2 … M+1 : A continuación aparecen $M$ líneas, cada una con una oferta. Una oferta está definida por dos enteros $C$ y $P$ separados por un espacio, donde $C \in \{1, 2\}$ representa la cantidad de personas por las cuales se hace la oferta, y $1 \le P \le 10^9$ es la cantidad de dinero que se ofrece.

Output

Línea 1 : Imprimir una línea con un entero, la máxima cantidad de dinero que puede recaudar el chofer.

Sample test(s)