Description
Kaykobad教授把为ACM选手买饭的任务交给了Nasa。Nasa决定买n种不同的食物。然后他询问了m名选手对每种食物的需求量。选手们当然不会给出任何符合逻辑的回答，他们只是想尽可能的多吃！Nasa很清楚，如果他们得到了想要的分量，他们就只会浪费粮食。Nasa决定不让这件事发生。
因此他机智的算出了对于每名选手吃一份每种食物能获得多少“满意值”。某人吃一份某种事物的满意值可能是零。如果每个人得到的总满意值超过上限，他就会浪费粮食。Nasa决定不让任何人得到的满意值超过该人的满意值上限。他计划，就算给某个人分数份食物，也不能让任何人的总满意值超过上限！
Nasa还决定给所有人买完全相同的套餐，这样就不会有人抱怨不公平。
在满足这些条件后，他最终意识到他的钱是无限的（反正可以找学校报销），因此他将会花尽可能多的钱。
Input
第一行有两个整数n，m（3<=n,m<=20），代表食物种类和人数。
第二行有n个实数，代表每种食物的单价。
接下来的m行每行描述一名选手：
这一行有个n+1个实数。前n个实数是他吃一份每种食物得到的满意值，第n个实数是他的满意值上限。
Output
按格式输出Nasa最多能花多少钱，向上取整。你可以假设不会有舍入误差问题。具体格式见样例。
Sample Input
3 3
1 0.67 1.67
1 2 1 430
3 0 2 460
1 4 0 420
Sample Output
Nasa can spend 1354 taka.
Hint
taka是孟加拉国的货币单位。
正解：线性规划，单纯形法。
最裸的线性规划，只要目标函数的系数全部乘m就行了。
//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1e18)
#define eps (1e-12)
#define il inline
#define RG register
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; double a[][];
int b[],n,m; il int gi(){
RG int x=,q=; RG char ch=getchar(); while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar(); while (ch>='' && ch<='') x=x*+ch-,ch=getchar(); return q*x;
} il void pivot(RG int l,RG int e){
RG double k=a[l][e]; a[l][e]=; for (RG int i=;i<=n;++i) a[l][i]/=k;
RG int len=; for (RG int i=;i<=n;++i) if (fabs(a[l][i])>eps) b[++len]=i;
for (RG int i=;i<=m;++i)
if (l!=i && fabs(a[i][e])>eps){
k=a[i][e],a[i][e]=;
for (RG int j=;j<=len;++j) a[i][b[j]]-=k*a[l][b[j]];
}
return;
} il double simplex(){
while (){
RG int l,e; for (e=;e<=n;++e) if (a[][e]>eps) break;
if (e==n+) return -a[][]; RG double tmp=inf;
for (RG int i=;i<=m;++i)
if (a[i][e]>eps && tmp>a[i][]/a[i][e]) tmp=a[i][]/a[i][e],l=i;
if (tmp==inf) return inf; pivot(l,e);
}
} il void work(){
n=gi(),m=gi(); for (RG int i=;i<=n;++i){ scanf("%lf",&a[][i]); a[][i]*=m; }
for (RG int i=;i<=m;++i){
for (RG int j=;j<=n;++j) scanf("%lf",&a[i][j]);
scanf("%lf",&a[i][]);
}
printf("Nasa can spend %0.0lf taka.",ceil(simplex())+eps); return;
} int main(){
File("satisfic");
work();
return ;
}