#1144. HOLES - Đào hố

Dọc đường cao tốc Hà Nội – Hải Phòng cần đào cái hố (để trồng cây tỏa bóng mát) bởi cái máy xúc. Các hố đánh số từ đến , các máy xúc đánh số từ đến . Thời gian để một máy xúc đào xong hố là phút.

Ban đầu, máy xúc thứ đang ở hố . Trước khi bắt đầu công việc hoặc sau khi đào xong hố của mình, máy xúc có thể di chuyển sang một hố bất kỳ khác. Thời gian để một máy xúc bất kỳ di chuyển giữa hai hố liền kề là phút. Như vậy, thời gian để máy xúc di chuyển từ hố sang hố là .

Yêu cầu: Tính thời gian ít nhất để các máy xúc đào được hố.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương
• Dòng tiếp theo chứa hai số nguyên dương
• Dòng tiếp theo chứa số nguyên dương, số thứ có giá trị tương ứng máy xúc đang ở hố . Các số trên một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

• Ghi ra một số nguyên dương duy nhất là thời gian nhỏ nhất để các máy xúc đào xong hố.

Ví dụ:

Dữ liệu vào:

3 4
2 3
3 1 3 3

Dữ liệu ra:

5

Dữ liệu vào:

2 1
1 1
1

Dữ liệu ra:

3

Giới hạn:

• số test tương ứng với số điểm có .