描述

一家银行计划安装一台取款机。这台机器能够为所请求的取款金额提供合适的钞票。该机器使用恰好 $N$ 种不同的钞票面额，记为 $D_k$，$k = 1, N$，并且对于每种面额 $D_k$，机器都有 $n_k$ 张钞票储备。例如：

$N = 3$，$n_1 = 10$，$D_1 = 100$，$n_2 = 4$，$D_2 = 50$，$n_3 = 5$，$D_3 = 10$

这意味着机器储备有 10 张面额为 100 的钞票、4 张面额为 50 的钞票以及 5 张面额为 10 的钞票。

设 $cash$ 为机器应交付的请求取款金额，编写一个程序，计算在不超过 $cash$ 的前提下，根据机器现有的钞票储备能够有效交付的最大金额。

注意：

“@” 是机器所交付货币的符号。例如，“@” 可以代表美元、欧元、英镑等。

输入

程序从标准输入读取数据。输入中的每个数据集代表一次特定的交易，格式如下：

$cash\ N\ n_1\ D_1\ n_2\ D_2\ \cdots\ n_N\ D_N$

其中，$0 \leq cash \leq 100000$ 是请求的取款金额，$0 \leq N \leq 10$ 是钞票面额的种类数，$0 \leq n_k \leq 1000$ 是面额为 $D_k$ 的钞票的可用数量，$1 \leq D_k \leq 1000$，$k = 1, N$。输入中的数字之间可以自由出现空格。输入数据是正确的。

输出

对于每组数据，程序将结果按如下示例所示，在标准输出的单独一行中打印。

输入数据 1

735 3  4 125  6 5  3 350
633 4  500 30  6 100  1 5  0 1
735 0
0 3  10 100  10 50  10 10

输出数据 1

735
630
0
0

提示

第一个数据集表示一次交易，请求的取款金额为 @735。机器包含 3 种钞票面额：4 张面额为 @125 的钞票、6 张面额为 @5 的钞票以及 3 张面额为 @350 的钞票。机器能够交付请求的准确金额。

在第二种情况下，机器的钞票储备无法满足请求的准确取款金额。能够交付的最大金额为 @630。请注意，机器中的钞票可能有多种组合方式来匹配交付的金额。

在第三种情况下，机器为空，不交付任何现金。在第四种情况下，请求的取款金额为 @0，因此机器不交付现金。

来源

2002 年东南欧竞赛