| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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: | adm |
| 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-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP 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 |
