1427: 一道水题
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:13
Solved:1
Description
如题,这是一道水题。
emaster的面前有 $n$ 杯水,第 $i$ 杯水的体积为 $a_{i}$,营养价值为 $b_{i}$。
今天是星期天,无聊的emaster发现了 $m$ 个空瓶,第 $i$ 个空瓶的体积为 $c_{i}$。emaster想装满所有空瓶并使得它们的所装的水的营养价值和最大。
emaster认为一杯水只有完全装入某个空瓶才能发挥功效,所以他不会将一杯水装入不同空瓶里,也不会只把一杯水的一部分装入空瓶。
输出emaster能使空瓶装满的最大营养价值和,如果无法装满所有空瓶,请输出 $-1$
Input
第一行,两个整数 $n,m$,依次代表水的杯数和空瓶的数量。
第二行,$m$ 个整数,第 $i$ 个整数 $c_{i}$ 代表第 $i$ 个空瓶的体积。
接下来 $n$ 行,每行两个整数 $a_{i}$ , $b_{i}$ ,依次代表第 $i$ 杯水的体积和营养价值。
数据范围:
$1 \le n,m \le 16$
$1 \le a_{i},b_{i},c_{i} \le 10^4$
Output
一行,一个整数。
代表emaster使空瓶装满的最大营养价值和,如果无法装满所有空瓶,输出 $-1$
Sample Input Copy
6 3
3 3 3
6 1000
1 20
2 20
3 50
1 40
3 100
Sample Output Copy
210