C - Penguin Skating Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

L 個のマスが横一列に並んでいます． マスは左から順に 1,2,\ldots,L と番号が振られています．

N 匹のペンギンがマス目の上にいます． ペンギンは左から順に 1,2,\ldots,N と番号が振られています． 最初，ペンギン i はマス A_i の上にいます． ここで，1 \leq A_1 < A_2 < \ldots < A_N \leq L です．

あなたは，次の操作を好きな回数行うことができます．

  • ペンギンを 1 匹選び，左または右へ向かって滑らせる． ペンギンは，目の前に空マスがある限り滑り続ける． 別のペンギンのいるマスの直前のマスに到達する，もしくは目の前にマスが存在しなくなったら，ペンギンは停止する．

例えば，N=3,L=10 で，ペンギンのいるマスが (2,3,7) であるとします． このとき，ペンギン 2 を右に滑らせると，ペンギン 2 はマス 6 まで移動します． また，ペンギン 3 を右に滑らせると，ペンギン 3 はマス 10 まで移動します．

あなたの目標は，すべての i について，ペンギン i がマス B_i の上にいるようにすることです． ここで，1 \leq B_1 < B_2 < \ldots < B_N \leq L です． 目標が達成可能か判定し，可能ならば必要な操作回数の最小値を求めてください．

制約

  • 1 \leq N \leq 10^5
  • N \leq L \leq 10^9
  • 1 \leq A_1 < A_2 < \ldots < A_N \leq L
  • 1 \leq B_1 < B_2 < \ldots < B_N \leq L
  • 入力される数はすべて整数．

入力

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

N L
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

目標が達成不可能な場合は -1 を，可能な場合は必要な操作回数の最小値を出力せよ．

入力例 1

4 11
3 4 6 10
1 5 6 11

出力例 1

3

次のように操作すればよいです．

  • ペンギン 1 を左に滑らせる．ペンギンの位置は，(1,4,6,10) になる．
  • ペンギン 2 を右に滑らせる．ペンギンの位置は，(1,5,6,10) になる．
  • ペンギン 4 を右に滑らせる．ペンギンの位置は，(1,5,6,11) になる．

入力例 2

1 3
1
2

出力例 2

-1

入力例 3

10 1000000000
65110170 68805223 123016442 275946481 661490312 760727752 764540566 929355340 930658577 947099792
1 2 123016442 661490311 929355337 930658574 999999997 999999998 999999999 1000000000

出力例 3

13

Score : 700 points

Problem Statement

There are L squares lining up horizontally in a row, numbered 1, 2, \ldots, L from left to right.

On those squares are N penguins, numbered 1, 2, \ldots, N from left to right. Initially, Penguin i is on Square A_i. Here, 1 \leq A_1 < A_2 < \ldots < A_N \leq L holds.

You can do the following operations any number of times:

  • Choose one penguin and slide it to the left or the right. The penguin will keep sliding as long as there is an empty square ahead. It will stop when it reaches a square just before a square occupied by another penguin, or there is no square ahead.

For example, assume that N=3, L=10, and the penguins are on the squares (2,3,7). Here, if we slide Penguin 2 to the right, it will move to Square 6; if we slide Penguin 3 to the right, it will move to Square 10.

Your objective is to put Penguin i on Square B_i for every i. Here, 1 \leq B_1 < B_2 < \ldots < B_N \leq L holds. Determine whether the objective is achievable. If it is achievable, find the minimum number of operations needed.

Constraints

  • 1 \leq N \leq 10^5
  • N \leq L \leq 10^9
  • 1 \leq A_1 < A_2 < \ldots < A_N \leq L
  • 1 \leq B_1 < B_2 < \ldots < B_N \leq L
  • All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

N L
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

Output

If the objective is unachievable, print -1; if it is achievable, print the minimum number of operations needed.

Sample Input 1

4 11
3 4 6 10
1 5 6 11

Sample Output 1

3

The following sequence of operations achieves the objective:

  • Slide Penguin 1 to the left. The penguins are now on the squares (1,4,6,10).
  • Slide Penguin 2 to the right. The penguins are now on the squares (1,5,6,10).
  • Slide Penguin 4 to the right. The penguins are now on the squares (1,5,6,11).

Sample Input 2

1 3
1
2

Sample Output 2

-1

Sample Input 3

10 1000000000
65110170 68805223 123016442 275946481 661490312 760727752 764540566 929355340 930658577 947099792
1 2 123016442 661490311 929355337 930658574 999999997 999999998 999999999 1000000000

Sample Output 3

13