You have been given 2 arrays A and B each of size N, and an integer X. Now, you need to pick a subset of k indices (maybe with repetitions) $(i_1 , i_2 , i_3 ... i_k)$ , such that :

$1 \le k \le N$

$A[i_1]+A[i_2]+A[i_3]+...+A[i_k] \le X$

$B[i_1]+B[i_2]+B[i_3]+...+B[i_k]$ is maximized.

You need to find and print the maximum possible value of $B[i_1]+B[i_2]+B[i_3]+...+B[i_k]$ such that $A[i_1]+A[i_2]+A[i_3]+...+A[i_k] \le X$ . Can you do it ?

Note that a single index can be picked multiple number of times to be part of the subset $(i_1,i_2,i_3...i_k)$

Input Format :

The first line contains a single integer X

The next line contains a single integer N.

Each of the next N lines contains 2 space separated integers, where the integers on the $i^{th}$ line denote $A[i]$ and $B[i]$.

Output Format :

Print the required answer on a single line.

Constrains:

$1 \le X \le 1000$

$1 \le N, A[i],B[i] \le 1000$