AT_arc105_c [ARC105C] Camels and Bridge

[problemUrl]: https://atcoder.jp/contests/arc105/tasks/arc105_c $ 1 $ から $ N $ の番号がついた $ N $ 頭のラクダがいます。 ラクダ $ i $ の体重は $ w_i $ です。 あなたはラクダたちに隊列を組ませ、$ M $ 個のパーツからなる橋を渡らせようとしています。 あなたは橋を渡る前にラクダたちの隊列を決め(番号の昇順となる必要はありません)、ラクダどうしを任意の非負の実数の間隔で並ばせることができます。 ラクダたちはこの決められた間隔を保って橋を渡ります。 橋の $ i $ 番目のパーツは長さ $ l_i $ で耐荷重は $ v_i $ です。 パーツ内部(両端を除く)にいるラクダたちの体重の総和が $ v_i $ より大きくなると、橋は崩落してしまいます。 橋が崩落しないようにラクダたちを渡らせることが可能かどうかを判定し、可能ならばそのときの先頭のラクダと末尾のラクダの距離としてありうる値の最小値を求めてください。 これは整数になることが証明できるので、整数で出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ w_1 $ $ w_2 $ $ \cdots $ $ w_N $ $ l_1 $ $ v_1 $ $ \vdots $ $ l_M $ $ v_M $

どのようにしても橋が崩落してしまう場合、`-1` を出力せよ。 そうでない場合、橋が崩落しないようにラクダたちを渡らせるときの先頭のラクダと末尾のラクダの距離としてありうる値の最小値を出力せよ。

### 制約 - 与えられる入力は全て整数 - $ 2\ \leq\ N\ \leq\ 8 $ - $ 1\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ w_i,l_i,v_i\ \leq\ 10^8 $ ### Sample Explanation 1 \- 例えば、先頭から順に $ 1,3,2 $ の順番に並べ、ラクダどうしの間隔をそれぞれ $ 0,10 $ にすることで橋が崩落しないようにラクダたちを渡らせることが可能です。 - パーツ $ 1 $ ではラクダ $ 1,3 $ あるいはラクダ $ 2 $ のみがパーツの内部にいる状態が起こります。どちらもパーツの内部にいるラクダたちの体重の総和がパーツ $ 1 $ の耐荷重である $ 4 $ 以下のため、橋が崩落することはありません。 - パーツ $ 2 $ ではラクダ $ 1,3 $ あるいはラクダ $ 2 $ のみがパーツの内部にいる状態が起こります。どちらもパーツの内部にいるラクダたちの体重の総和がパーツ $ 1 $ の耐荷重である $ 6 $ 以下のため、橋が崩落することはありません。 - ラクダどうしの間隔が $ 0 $ でもよいこと、パーツの内部はパーツの両端を含まないことに注意してください。 ### Sample Explanation 2 \- どのようにしても橋が崩落してしまう場合は `-1` を出力してください。