Khóa số

View as PDF

Submit solution


Points: 0.62 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 ~a_1~, ~a_2~, ..., ~a_n~, các số nằm trong phạm ~v_i~ 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 ~b_1~, ~b_2~, ..., ~b_n~ 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 ~b_1~, ~b_2~, ..., ~b_n~.

Yêu cầu: Cho hai dãy số nguyên ~a_1~, ~a_2~, ..., ~a_n~, ~b_1~, ~b_2~, ..., ~b_n~ 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 ~a_1~, ~a_2~, ..., ~a_n~ ~(a_n \leq k)~;
  • Dòng thứ ba chứa ~n~ số nguyên không âm ~b_1~, ~b_2~, ..., ~b_n~ ~(b_n \leq k)~

Output

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

Giới hạn

  • Có ~20\%~ số test ứng với ~20\%~ số điểm có ~n = 3~ và ~k \leq 10~;
  • Có ~40\%~ số test ứng với ~40\%~ số điểm có ~n \leq 30~ và ~k \leq 1000~;
  • Có ~40\%~ số test còn lại ứng với ~40\%~ số điểm có ~n \leq 300~ và ~k \leq 10^{6}~

Sample Input

3 10
10 9 0
1 0 0

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.