g6-08105. 礼盒分装 未做

食品厂要把 $n$ 个单位的原料分装成恰好 $k$ 盒，每盒都要装满，不许剩下。厂里只有 $m$ 种规格的盒子：第 $i$ 种装 $s_i$ 个单位，整盒能卖 $v_i$ 元；同一种盒子想用几盒用几盒，盒子之间不分先后。求最多能卖多少钱；如果怎么装都凑不出恰好 $k$ 盒，输出 $-1$。

第一行三个整数 $n$、$k$、$m$。

接下来 $m$ 行，每行两个整数 $s_i$、$v_i$。

一行一个整数，表示最大总售价；无法恰好拆成 $k$ 份时输出 $-1$。

输入 1

10 3 3
2 4
3 5
4 7

输出 1

18

恰好 3 盒可以装 $2+4+4$，卖 $4+7+7=18$ 元；若装成 5 盒 $2+2+2+2+2$ 能卖 20 元，但那不是 3 盒，所以答案是 18。

$1\le n\le 500$，$1\le k\le 50$，$1\le m\le 20$，$1\le s_i\le n$，$0\le v_i\le 10^4$。保证答案在 64 位整数范围内。