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.|

P143SUMI - ROUND 3I - Cái túi

Một cửa hàng vàng bạc đá quý bị ăn trộm. Tên trộm này chỉ để ý đến những viên kim cương mà thôi. Trong cửa hàng này có N viên kim cương, mỗi viên có khối lượng và giá trị nhất định.

Tên trộm mang đi K cái túi, mỗi cái túi có giới hạn khối lượng nhất định. Để tránh kim cương bị trầy xước, tên trộm quyết định mỗi chiếc túi chỉ được để tối đa 1 viên kim cương.

Các bạn hãy tính toán xem tên trộm này có thể mang đi được tổng tài sản lớn nhất là bao nhiêu?

Input

Dòng đầu tiên gồm 2 số nguyên N và K (N, K <= 300 000).

N dòng tiếp theo, mỗi dòng gồm 2 số M_i và V_i, lần lượt là khối lượng và giá trị của viên kim cương thứ i. (M_i, V_i <= 1 000 000).

K dòng tiếp theo, mỗi dòng chứa một số nguyên C_i, là giới hạn khối lượng của cái túi thứ i. (C_i <= 100 000 000).

Output

In ra tổng giá trị thiệt hại lớn nhất của cửa hàng này.

Example

Test 1

Input:

2 1
5 10
100 100
11

Output:

10

Test 2

Input:

3 2
1 65
5 23
2 99
10
2

Output:

164


Được gửi lên bởi:Admin
Ngày:2014-07-08
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:ASM32 ASM32-GCC MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2015-07-07 09:11:22 Nguyễn Ðình Vinh
quy hoạch động :3
2015-05-20 17:29:55 Nguyễn Vĩnh Thịnh
?

Last edit: 2017-02-11 06:41:01
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.