HZNUOJ

ZKL的减肥计划

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:111     AC:51     Score:99.87

Description

ZKL减肥  越减越肥

ZKL正在完成自己的减肥计划。为了减肥,ZKL希望吃到更少的脂肪。然而也不能只吃低脂肪食品,因为那样的话就会导致营养跟不上,体质变差。

通过研究发现:人体需要的营养素有40多种,自然界没有任何一种食物能全面提供这许多营养素。要吃好,就要讲究膳食营养结构的合理和平衡,才能获得这许多营养素。比如就一顿饭来说,肉类至少需要吃 1 份,鱼类至少需要吃 1 份,蛋类至少需要吃 1 份,蔬菜类至少需要吃 2 份。

因为ZKL的数学不太好,现在需要聪明的你告诉ZKL在营养膳食的情况下吃到最少的脂肪是多少? 或者 告诉他无法达到营养膳食

Input

第一行包含两个正整数 $n$ 和 $k$ $n$表示$n$个食品供小张选择,而这$n$个食品被分为$k$ 类。($1$<=$n$<=$1000$,$1$<=$k$<=$n$)

第二行包含  $k$ 个不超过 $n$ 的非负整数,相应的表示ZKL需要吃 $1$ 到  $k$类食品的最少份数。

接下来 $n$ 行每行包括$2$个正整数 $a_i$ , $b_i$分别表示该食品的脂肪指数和所属的类别 。($0$<=$a_i$<=$100000$,$1$<=$b_i$<=$k$

Output

在满足营养膳食的条件下ZKL吃到的最少脂肪指数和。

若ZKL不可能达到营养膳食这个条件就输出 “MDJL!!!”(不包括引号)

Samples

input
3 2 1 1 2 1 3 2 4 1
output
5
input
2 2 1 1 1 2 1 2
output
MDJL!!!
input
2 1 2 2 1 2 1
output
4

Hint

第一组样例 ZKL可以选择第一个食物和第二个食物取得最优,2+3=5

第二组样例 因为两个食物都属于第二类,但是第一类食物又至少需要吃一份,所以不可能达到平衡膳食。

第三组样例 选择仅有的两个食物正好能满足要求,所得脂肪数为 2+2 = 4

注意每一个食物要么吃,要么不吃,不能只吃一部分。

Author

QIU, Longfeng