线性空间向量基底板子。
不同于异或空间的线性基。
我们考虑求出这些向量的基底，我们只要按照价值小的先插即可，最后选择 \(k\) 个向量底即可。
我们发现如果一个向量可能成为底，则他的价值一定最小。
#pragma optimize(2)
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
x=0;char c=getchar();bool f=false;
for(;!isdigit(c);c=getchar())f!=c==‘-‘;
for(;isdigit(c);c=getchar())x=x*10+c-‘0‘;
if(f)x=-x;
}
template<typename T ,typename ...Arg>
inline void read(T &x,Arg &...args){
read(x);read(args...);
}
template<typename T>
inline void write(T x){
if(x<0)putchar(‘-‘),x=-x;
if(x>=10)write(x/10);
putchar(x%10+‘0‘);
}
const int max_wei=700;
const long double eps=1e-5;
int n,m,num=0,cost=0;;
template<class T>
struct Vector{
T a[max_wei];
void init(){for(int i=0;i<m;i++)a[i]=0;}
Vector operator+(const Vector b)const{
Vector<T> c;c.init();for(int i=0;i<m;i++)
c.a[i]=a[i]+b.a[i];return c;
}
Vector operator-(const Vector b)const{
Vector<T> c;c.init();for(int i=0;i<m;i++)
c.a[i]=a[i]-b.a[i];return c;
}
Vector operator*(T x)const{
Vector<T> c;c.init();for(int i=0;i<m;i++)
c.a[i]=a[i]*x;return c;
}
};
struct Leaner_Basis{
Vector<long double>b[max_wei];
bool insert(Vector<long double> c){//将向量c插入线性基 并返回能否插入
for(int i=m-1;i>=0;i--) {
if(abs(c.a[i])<eps)continue;
if(abs(b[i].a[i])<eps){b[i]=c;return true;}
long double t=c.a[i]/b[i].a[i];
c=c-b[i]*t;
}
return false;
}
}B;
struct node{
int cost;
Vector<long double>c;
bool operator<(const node b)const{
return cost<b.cost;}
}a[500+10];
signed main(){
//freopen("buy.in","r",stdin);
//freopen("buy.out","w",stdout);
read(n,m);
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
read(a[i].c.a[j]);
for(int i=1;i<=n;i++)
read(a[i].cost);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
if(B.insert(a[i].c))
num++,cost+=a[i].cost;
printf("%d %d",num,cost);
}