[Uva 10498]满意值

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file happiness.in Output file happiness.out

【题目描述】

Kaykobad教授把为ACM选手买饭的任务交给了Nasa。Nasa决定买n种不同的食物。然后他询问了m名选手对每种食物的需求量。选手们当然不会给出任何符合逻辑的回答,他们只是想尽可能的多吃!Nasa很清楚,如果他们得到了想要的分量,他们就只会浪费粮食。Nasa决定不让这件事发生。

因此他机智的算出了对于每名选手吃一份每种食物能获得多少“满意值”。某人吃一份某种事物的满意值可能是零。如果每个人得到的总满意值超过上限,他就会浪费粮食。Nasa决定不让任何人得到的满意值超过该人的满意值上限。他计划,就算给某个人分数份食物,也不能让任何人的总满意值超过上限!

Nasa还决定给所有人买完全相同的套餐,这样就不会有人抱怨不公平。

在满足这些条件后,他最终意识到他的钱是无限的(反正可以找学校报销),因此他将会花尽可能多的钱。

【输入格式】

第一行有两个整数n,m(3<=n,m<=20),代表食物种类和人数。

第二行有n个实数,代表每种食物的单价。

接下来的m行每行描述一名选手:

这一行有个n+1个实数。前n个实数是他吃一份每种食物得到的满意值,第n个实数是他的满意值上限。

【输出格式】

按格式输出Nasa最多能花多少钱,向上取整。你可以假设不会有舍入误差问题。具体格式见样例。

【样例输入】

3 3

1 0.67 1.67

1 2 1 430

3 0 2 460

1 4 0 420

【样例输出】

Nasa can spend 1354 taka.

【提示】

taka是孟加拉国的货币单位。

【来源】

Uva 10498 Happiness

Problemsetter: Mustaq Ahmed, University of Waterloo