510001 - 满意值

【题目描述】满意值(happiness)

琳琳要为m名选手参赛选手买n种不同的食物,并且所有人都是同样的套餐。 每名选手吃一份每种食物能获得一定的“满意值”,某人吃一份某种食物的满意值可能是零。如果每个人得到的总满意值超过上限,他就会浪费粮食。琳琳决定不让任何人得到的满意值超过该人的满意值上限。她计划,就算给某个人分数份食物,也不能让任何人的总满意值超过上限! 在满足这些条件后,因为可以找学校报销,所以理论上她的钱是无限的,因此她将会花尽可能多的钱。

输入

第一行有两个整数n,m(3≤n,m≤20),代表食物种类和人数。 第二行有n个实数,代表每种食物的单价。
接下来的m行每行描述一名选手: 这一行有个n+1个实数。前n个实数是他吃一份每种食物得到的满意值,第n个实数是他的满意值上限。

输出

按格式输出琳琳最多能花多少taka(孟加拉国的货币单位),向上取整。你可以假设不会有舍入误差问题。具体格式见样例。

样例

输入

3 3 
1 0.67 1.67 
1 2 1 430 
3 0 2 460 
1 4 0 420

输出

Nasa can spend 1354 taka.
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题