/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
1 から N まで番号がつけられた N 個のマスが一列に並んでいます。最初、 M 個のマスに石が入っており、マス X_i には A_i 個 (1 \leq i \leq M) の石が入っています。
あなたは以下の操作を好きな回数( 0 回でもよい)行うことができます。
- マス i (1 \leq i \leq N-1) に石があるとき、マス i から石を 1 つマス i+1 に移動させる。
N 個のマスすべてに石がちょうど 1 個ずつ入っている状態にするために必要な操作回数の最小値を求めてください。ただし、不可能な場合は -1 を出力してください。
制約
- 2 \leq N \leq 2 \times 10^{9}
- 1 \leq M \leq 2 \times 10^{5}
- M \leq N
- 1 \leq X_i \leq N (1 \leq i \leq M)
- X_i \neq X_j (1 \leq i < j \leq M)
- 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 X_2 \ldots X_M A_1 A_2 \ldots A_M
出力
答えを出力せよ。
入力例 1
5 2 1 4 3 2
出力例 1
4
以下の 4 回の操作で、5 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることができます。
- マス 1 の石を 1 つマス 2 に移動させる。
- マス 2 の石を 1 つマス 3 に移動させる。
- マス 4 の石を 1 つマス 5 に移動させる。
- マス 1 の石を 1 つマス 2 に移動させる。
また、3 回以下の操作では 5 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることはできません。よって、4 を出力します。
入力例 2
10 3 1 4 8 4 2 4
出力例 2
-1
どのように操作を行っても 10 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることはできません。よって、-1 を出力します。
Score : 300 points
Problem Statement
There are N cells numbered from 1 to N in a row. Initially, M cells contain stones, and cell X_i contains A_i stones (1 \leq i \leq M).
You can perform the following operation any number of times (possibly zero):
- If cell i (1 \leq i \leq N-1) contains a stone, move one stone from cell i to cell i+1.
Find the minimum number of operations required to reach a state where each of the N cells contains exactly one stone. If it is impossible, print -1.
Constraints
- 2 \leq N \leq 2 \times 10^{9}
- 1 \leq M \leq 2 \times 10^{5}
- M \leq N
- 1 \leq X_i \leq N (1 \leq i \leq M)
- X_i \neq X_j (1 \leq i < j \leq M)
- 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M X_1 X_2 \ldots X_M A_1 A_2 \ldots A_M
Output
Print the answer.
Sample Input 1
5 2 1 4 3 2
Sample Output 1
4
You can reach a state where each of the five cells contains exactly one stone with four operations as follows:
- Move one stone from cell 1 to cell 2.
- Move one stone from cell 2 to cell 3.
- Move one stone from cell 4 to cell 5.
- Move one stone from cell 1 to cell 2.
It is impossible to achieve the goal in three or fewer operations. Therefore, print 4.
Sample Input 2
10 3 1 4 8 4 2 4
Sample Output 2
-1
No matter how you perform the operations, you cannot reach a state where all ten cells contain exactly one stone. Therefore, print -1.