No.1008 Bench Craftsman

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 57
作問者 : CinnamorollCinnamoroll / テスター : IKyoproIKyopro
10 ProblemId : 2963 / 出題時の順位表
問題文最終更新日: 2020-03-08 00:41:46

問題文

$N$個の区画からなるベンチがあり、ベンチの左から$i$番目の区画の耐荷重は$a_i$です。 このベンチには$M$人の人が座ることがわかっており、人$j$は左から$x_j$番目の区画に座り,体重が$w_j$です。

左から$i$番目の区画の負荷は、ベンチの耐久度を$c$として ${\displaystyle \sum_{j = 1} ^{M} max(0,w_j-abs(i-x_j)·c)}$ で定義されます。 左から$i$番目の区画であって、$a_i$以上の負荷がかかるような$i$が存在するときベンチは壊れてしまいます。
また、同じ区間に複数の人が座ることがあります。
熟練したベンチ職人であるCinnamorollさんは、ベンチを改修することで耐久度$c$を任意の非負整数に変化させることができます。 ベンチが壊れないようにするために必要な耐久度$c$の最小値を求めてください。 そのような$c$が存在しない場合は-1を出力してください。

入力

$N~~~M$
$a_1~~a_2~~...~~a_N$
$x_1~~w_1$
$x_2~~w_2$
$...$
$x_M~~w_M$

$1 \leq N,M \leq 10^5$
$1 \leq a_i \leq 10^9~~(a_1,a_2,...,a_N)$
$1 \leq x_j \leq N~~~~(x_1,x_2,...,x_M)$
$1 \leq w_j \leq 10^5~~(w_1,w_2,...,w_M)$
入力は全て整数である

出力

必要な耐久度の最小値を出力してください。条件を満たす耐久度が存在しない場合は-1を出力してください。最後に改行してください。

サンプル

サンプル1
入力
4 3
11 13 12 17
1 8
3 2
4 7
出力
2

耐久度が0の場合の負荷は(17,17,17,17)ですべての区画で条件を満たしません。
耐久度が1の場合の負荷は(12,13,14,13)で区画1,区画2,区画3で条件を満たしません。
耐久度が2の場合の負荷は(9,9,11,9)で条件を満たします。

サンプル2
入力
5 1
4 6 5 8 2
2 1
出力
0

耐久度は0でも構いません。

サンプル3
入力
1 1
1
1 100
出力
-1

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。