g6-08113. 布头清货 未做

布店有一块长 $n$ 米的布料。仓库里存着 $m$ 种布头：第 $i$ 种长 $l_i$ 米、能卖 $v_i$ 元，每种都只剩一段，卖掉就没了。要用这些布头恰好拼出长 $n$ 米的布（每种布头最多用一次，段与段之间不分先后），求最多能卖多少钱；如果怎么拼都拼不出正好的长度，输出 $-1$。

第一行两个整数 $n$、$m$。

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

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

输入 1

12 4
3 5
5 9
4 7
2 3

输出 1

21

选长 3、4、5 米的三段布头：$3+4+5=12$ 米正好拼满，能卖 $5+7+9=21$ 元。

$1\le n\le 200$，$1\le m\le 20$，$1\le l_i\le n$，$l_i$ 互不相同，$0\le v_i\le 10^4$。保证答案在 64 位整数范围内。