Closest Cow Wins

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Trên một trục số có $K$ bãi cỏ, bãi thứ $i$ ở vị trí $p_{i}$ với độ ngon $t_{i}$ . Đối thủ Nhoj đã đặt $M$ con bò tại các vị trí $f_{1}, f_{2}, \dots, f_{M}$ .

FJ cần đặt $N$ con bò của mình lên trục số (vị trí không nhất thiết là số nguyên). Một bãi cỏ thuộc về người chơi nào có con bò gần nhất với bãi đó. Nếu khoảng cách bằng nhau, bãi thuộc về Nhoj.

Hãy tìm tổng độ ngon lớn nhất mà FJ có thể thu được.

Dữ liệu vào

Dòng $1$ : Ba số nguyên $K$ , $M$ , $N$ .
$K$ dòng tiếp: Mỗi dòng gồm hai số nguyên $p_{i}$ và $t_{i}$ .
$M$ dòng tiếp: Mỗi dòng gồm một số nguyên $f_{i}$ .

Dữ liệu ra

In ra tổng độ ngon lớn nhất FJ thu được.

Ràng buộc

$1 \leq K, M, N \leq 2 \times 10^{5}$ .
$0 \leq p_{i}, f_{i} \leq 10^{9}$ .
$0 \leq t_{i} \leq 10^{9}$ .
Tất cả vị trí đôi một phân biệt.

Ví dụ

Input	Output	Giải thích
6 5 2 0 4 4 6 8 10 10 8 12 12 13 14 2 3 5 7 11	36	Đặt bò tại $11.5$ và $8$ , thu được các bãi có độ ngon $10 + 12 + 14 = 36$ .

Bình luận

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