시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 0 0 0 0.000%

문제

The elusive Phantom Thief Lupin the Fourth (usually addressed as just Lupin) has taken on the daunting task of breaking into the vault of the largest, most majestic, most technologically advanced castle in the world: The Castle of Gagliostro. Equipped with state of the art technology, it goes without saying that the castle has top-class security which fully utilises the capabilities of man and machine. Nevertheless, Lupin was unfazed even when faced when such a challenge. He stealthily evaded the guards and security cameras positioned around the castle, fought through numerous traps, and solved many puzzles before finally arriving at the vault, where he hacked the security cameras to show a feed that is not at all suspicious and drugged the security guards to render all of them unconscious.

The final obstacle standing in his way is an electronic password system which will open the vault once the correct password is entered. Initially, N non-negative integers between 0 and K inclusive are shown on the screen, the ith of which is equal to Ai. The password also consists of N numbers, each of which is also a non-negative integer between 0 and K inclusive. Through his sheer, blinding brilliance in both mind and body, Lupin determined that the ith number in the password is Pi for each 1 ≤ i ≤ N. Upon figuring out the password, Lupin was elated and all ready to complete his mission. To his dismay, however, the way the password is input is rather peculiar, and very time consuming, involving operations which alter the numbers shown on the screen slowly but surely.

Suppose the ith number currently shown on the screen is Ci (1 ≤ i ≤ N). Lupin can open the vault when Ci = Pi for all 1 ≤ i ≤ n. Otherwise, Lupin is allowed operations of the following form: choose two integers i, j with 1 ≤ i ≤ j ≤ N, and for all integers l with i ≤ l ≤ j, Cl changes to Cl + 1 (mod K + 1). In other words, change Cl to the remainder of Cl + 1 when it is divided by K + 1. Specifically, 0 changes to 1, 1 changes to 2, . . . , K − 1 changes to K and K changes to 0.

As if the terrible password input system wasn’t bad enough, Lupin has also received information that his archnemesis Inspector Zenigada is rushing over to catch him once and for all. In order to break into the vault and escape as quickly as possible, Lupin wants to use the minimum number of operations needed to change the initial numbers to become the password and open the vault; your task is to determine the minimum number of operations Lupin needs.

입력

Your program must read from standard input.

The first line of the input contains two integers, N and K.

The next line contains N integers A1, A2, . . . , AN, where Ai is the ith number shown on the screen initially.

The third and final line contains N integers P1, P2, . . . , PN, where Pj is the jth number in the password.

출력

Your program must print to standard output.

The output should contain a single integer on a single line, the minimum number of operations Lupin needs to change the numbers on the screen to become the password.

제한

  • 1 ≤ N ≤ 3 × 105
  • 0 ≤ K ≤ 109
  • 0 ≤ A[i], P[i] ≤ K for all 1 ≤ i ≤ N

서브태스크

번호 배점 제한
1 6

N ≤ 3

2 5

Ai ≤ Ai+1 for all 1 ≤ i ≤ N − 1, Pi = 0 for all 1 ≤ i ≤ N

3 9

K ≤ 1

4 10

N, K ≤ 80

5 13

N ≤ 400

6 23

N ≤ 3000

7 34

예제 입력 1

3 4
1 2 0
2 1 2

예제 출력 1

4

An optimal sequence of operations is to choose (i, j) = (1, 3) once, (2, 3) once and (2, 2) twice.

예제 입력 2

7 1
1 0 1 0 1 1 1
0 0 1 1 0 1 0

예제 출력 2

3

An optimal sequence of operations is to choose (i, j) = (1, 3) once, (2, 6) once and (6, 7) once.

예제 입력 3

7 9
1 5 3 4 8 3 2
7 4 8 3 2 3 1

예제 출력 3

18

채점 및 기타 정보

  • 예제는 채점하지 않는다.