Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DHLOCK - Khóa số

Bạn nhận được một hộp quà với một khóa số ở bên ngoài. Thông tin hiển thị trên khóa là một dãy n số nguyên a1, a2,..., an, các số nằm trong phạm vi từ 0 đến k. Có (n+2) phím dùng để thay đổi giá trị các số, một phím nằm bên trái khóa, một phím nằm bên phải khóa, dưới mỗi số có một phím. Bạn nhanh chóng nhận ra rằng:

-          Khi bấm vào phím nằm bên trái khóa thì giá trị tất cả các số trên khóa tăng lên 1, nếu số nào đang có giá trị là k thì sau khi bấm nó nhận giá trị 0. Ví dụ, nếu dãy là (10, 9, 0) và k = 10, khi bấm vào phím nằm bên trái khóa thì trạng thái mới của dãy là (0, 10, 1).

-          Khi bấm vào phím nằm bên phải khóa thì tất cả các số dịch chuyển đi sang bên phải, trừ số cuối cùng, số cuối cùng trở thành số đầu tiên. Ví dụ, nếu dãy là (10, 9, 0) và k = 10, khi bấm vào phím nằm bên phải khóa thì trạng thái mới của dãy là (0, 10, 9).

-          Khi bấm vào phím nằm bên dưới số thứ i (i=1, 2,..., n) thì giá trị số thứ i trên khóa tăng lên 1, nếu số đang có giá trị là k thì sau khi bấm nó nhận giá trị 0. Ví dụ, nếu dãy là (10, 9, 0) và k = 10, khi bấm vào phím nằm bên dưới số thứ 2 thì trạng thái mới của dãy là (10, 10, 0).

Trên tờ bưu thiếp gửi kèm chiếc hộp có ghi một dãy n số nguyên b1, b2,..., bn chính là mật mã để mở được chiếc hộp. Chiếc hộp sẽ được mở nếu thông tin hiển thị trên khóa số là dãy b1, b2,..., bn.

Yêu cầu: Cho hai dãy số nguyên a1, a2,..., an, b1, b2,..., bn và số nguyên dương k, hãy tìm cách bấm ít lần nhất để mở được chiếc hộp.

Input

-          Dòng đầu chứa hai số nguyên dương n, k;

-          Dòng thứ hai chứa n số nguyên không âm a1, a2,..., an (an k);

-          Dòng thứ ba chứa n số nguyên không âm b1, b2,..., bn (bn k)

Output

Một số nguyên là số lần bấm ít lần nhất để mở được chiếc hộp

Example

Input:

3 10

10 9 0

1 0 0 Output: 3

Ghi chú:

  • Có 20% số test ứng với 20% số điểm có n = 3 và k ≤ 10;
  • Có 40% số test ứng với 40% số điểm có n ≤ 30 và k ≤ 1000;
  • Có 40% số test còn lại ứng với 40% số điểm có n ≤ 300 và k ≤ 106

Được gửi lên bởi:VOJ Team
Ngày:2015-04-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:Duyên Hải khối 10 năm 2015

hide comments
2016-04-18 15:26:47 xin đừng quên tôi
Tham khảo thuận toán và code tại: http://yeulaptrinh.pw/86/spoj-dhlock/
2015-11-15 02:32:55
mọi người tham khảo cách làm này: http://www.oni.vn/IQXfQ
2015-07-10 10:37:07 N�ng D�n John
Bài này dễ chết thặc :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.