Cash Machine

A bank plans to install a cash-withdrawal machine. For a requested amount, the machine delivers bills from its supply. It uses exactly $N$ distinct denominations $D_1, D_2, \dots, D_N$, and for each denomination $D_k$ it holds a supply of $n_k$ bills.

For example, $N = 3$ with $(n_1, D_1) = (10, 100)$, $(n_2, D_2) = (4, 50)$, $(n_3, D_3) = (5, 10)$ means the machine holds 10 bills of denomination 100, 4 bills of denomination 50, and 5 bills of denomination 10.

Let $\mathit{cash}$ be the requested amount. Write a program that computes the maximum amount not exceeding $\mathit{cash}$ that the machine can deliver using its available bills.

The input contains several data sets and is read until end-of-file. Each data set describes one transaction in the form

cash N n1 D1 n2 D2 ... nN DN

where $0 \le \mathit{cash} \le 100000$ is the requested amount, $0 \le N \le 10$ is the number of denominations, $0 \le n_k \le 1000$ is the number of available bills of denomination $D_k$, and $1 \le D_k \le 1000$ for $k = 1, \dots, N$. Whitespace may appear freely between the numbers. The input is always well-formed.

For each data set, print on its own line the maximum amount of cash, not exceeding the requested amount, that the machine can deliver.

If the requested amount cannot be formed exactly, deliver the largest amount that does not exceed it. If the machine has no bills to offer (for example $N = 0$) or the requested amount is $0$, the delivered amount is $0$. Several different bill combinations may add up to the same delivered amount.