Săn Kho Báu

Điểm: 7,00 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Bạn đang ở trên một hòn đảo được biểu diễn bởi một lưới $n \times m$ . Các hàng được đánh số từ $1$ đến $n$ , các cột từ $1$ đến $m$ . Trên đảo có $k$ kho báu, kho báu thứ $i$ nằm tại ô $(r_{i}, c_{i})$ .

Ban đầu bạn đứng ở góc dưới bên trái của lưới, tức ô $(1, 1)$ . Nếu tại bất kỳ thời điểm nào bạn đứng trên một ô chứa kho báu, bạn nhặt nó mà không tốn thêm thời gian. Trong một bước di chuyển, bạn có thể đi lên (từ $(r, c)$ sang $(r + 1, c)$ ), trái (từ $(r, c)$ sang $(r, c - 1)$ ), hoặc phải (từ $(r, c)$ sang $(r, c + 1)$ ). Vì bẫy, bạn không thể đi xuống.

Tuy nhiên, đi lên cũng rất nguy hiểm. Bạn chỉ có thể đi lên khi đang ở một cột an toàn. Có $q$ cột an toàn: $b_{1}, b_{2}, \dots, b_{q}$ .

Hãy tính số bước di chuyển tối thiểu để thu thập tất cả các kho báu.

Dữ liệu vào

Dòng đầu chứa bốn số nguyên $n, m, k, q$ — số hàng, số cột, số kho báu và số cột an toàn.
$k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $r_{i}, c_{i}$ — tọa độ ô chứa kho báu thứ $i$ . Các kho báu nằm ở các ô phân biệt.
Dòng cuối cùng chứa $q$ số nguyên phân biệt $b_{1}, b_{2}, \dots, b_{q}$ — các cột an toàn.

Dữ liệu ra

In ra số bước di chuyển tối thiểu để thu thập tất cả các kho báu.

Ràng buộc

$2 \leq n, m, k, q \leq 2 \cdot 10^{5}$
$q \leq m$
$1 \leq r_{i} \leq n$ , $1 \leq c_{i} \leq m$
$1 \leq b_{i} \leq m$ , các $b_{i}$ phân biệt.

Ví dụ

Input	Output	Giải thích
3 6 3 2 1 6 2 2 3 4 1 6	15	Tối ưu: lấy kho báu tại $(1, 6)$ , đi lên hàng $2$ tại cột $6$ , lấy kho báu $(2, 2)$ , đi lên hàng $3$ tại cột $1$ , rồi lấy kho báu $(3, 4)$ — tổng cộng $15$ bước.
3 3 3 2 1 1 2 1 3 1 2 3	6	Dùng cột $2$ làm cột đi lên; mỗi hàng lấy kho báu ở cột $1$ .
3 5 3 2 1 2 2 3 3 1 1 5	8	Dùng cột $1$ làm cột đi lên là tối ưu.

Bình luận

Không có bình luận tại thời điểm này.