Will viajaba con su padre en una misión de reconocimiento en el espacio, la moderna nave espacial de Woll, el padre de Will, está circulando los alrededores del planeta Marte, sin embargo toda la tecnologia en la nave de Woll no es suficiente contra nuevas amenazas.

Durante su investigación la nave de Woll es soprendida por una tormenta espacial, que lo hace cambiar de curso, la tormneta es tan fuerte que la nave sufre daños severos y aterriza accdidentadamente sobre los llanos del planeta Tierra. Este planeta fué desahibitado hace muchos siglos cuando su población la contaminó totalmente.

A pesar del mal momento sufrido, will y woll han sobrevivido, sin embargo su suerte no puede ser peor. La nave se partió en dos al momento del aterrizaje, y la parte de la nave en la que se encuentran las provisiones para sobrevivir está a muchos kilomentros ahora.

Woll esta muy lastimado y no puede moverse, entonces ordena a su joven pero entrenado hijo ir por las provisiones para que ambos puedan sobrevivir hasta que sean rescatados. Las provisiones son alimentos en pequeños contenedores que contienen cápsulas, cada cápsula posee pastillas compuestas de proteinas.

El ambiente afuera es desconocido, y para sobrevivir se necesita de mucho oxígeno, más de lo que Will podría gastar. La misión de Will es llegar lo más rapido posible a la destrozada cola de la nave y extraer las provisiones necesarias para que él y su padre puedan sobrevivir.

En la cola de la nave hay M contenedores y en cada contenedor A cápsulas con B pastillas. Will lleva consigo una mochila con capacidad para N cápsulas, él no puede contar el número exacto de B pastillas, así que solo puede coger N cápsulas cuyo contenido total favorezca el máximo de pastillas que puede llevar. Ayuda a Will a cumplir con su misión.

Input

La primera línea del INPUT comienza con un número T que indica el número de casos del problema propuesto. (1 ≤ T ≤ 100)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

La primera línea de la entrada contiene el entero N ( 1 ≤ N ≤ 2 x 10 ^ 8 ) y el entero M ( 1 ≤ M ≤ 20 ).
Las siguientes M líneas contienen los números A y B, cada Ai y Bi del Mi contenedor (1 ≤ Ai ≤ 10 ^ 8, 1 ≤ Bi ≤ 10).

Output

Devolver el número máximo de pastillas que Will puede llevar.

Entrada de ejemplo