配点 : $200$ 点

問題文

高橋君の夏休みは $N$ 日間です。

夏休みの宿題が $M$ 個出されており、$i$ 番目の宿題をやるには $A_i$ 日間かかります。

複数の宿題を同じ日にやることはできず、また、宿題をやる日には遊ぶことができません。

夏休み中に全ての宿題を終わらせるとき、最大何日間遊ぶことができますか？

ただし、夏休み中に全ての宿題を終わらせることができないときは、かわりに -1 を出力してください。

制約

• $1 \leq N \leq 10^6$
• $1 \leq M \leq 10^4$
• $1 \leq A_i \leq 10^4$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$A_1$ $...$ $A_M$

出力

高橋君が遊ぶことのできる日数、または、-1 を出力せよ。

41 2
5 6

30

例えば、最初の $5$ 日間で $1$ 番目の宿題をやり、その後 $30$ 日間遊んで、最後の $6$ 日間で $2$ 番目の宿題をやることで、$30$ 日間遊ぶことができます。

10 2
5 6

-1

宿題を終わらせることができません。

11 2
5 6

0

宿題を終わらせることはできますが、遊ぶことはできません。

314 15
9 26 5 35 8 9 79 3 23 8 46 2 6 43 3

9