program ex;

const
  maxn=2000;
  maxm=50;
  zero=1e-15;

var
  g: Array[0..maxn, 1..maxm] of extended;
  cost: Array[1..maxn] of longint;
  from: Array[1..maxn] of longint;
  n, m: longint;
  ans: longint;
  num: Array[1..maxm] of longint;
  tot: longint;
  kk: Array[1..maxn] of longint;

procedure init;
var
  i, j: longint;
begin
  read(n, m);
  for i:=1 to n do
    for j:=1 to m do
      read(g[i, j]);
  for i:=1 to n do begin
    read(cost[i]);
    from[i]:=i;
  end;
end;

procedure qsort(l, r: longint);
var
  i, j: longint;
  x, y: longint;
  t: longint;
begin
  i:=l;
  j:=r;
  x:=cost[(l+r) shr 1];
  y:=from[(l+r) shr 1];
  while i<=j do begin
    while (cost[i]<x)or(cost[i]=x)and(from[i]<y) do inc(i);
    while (cost[j]>x)or(cost[j]=x)and(from[j]>y) do dec(j);
    if i<=j then begin
      g[0]:=g[i];
      g[i]:=g[j];
      g[j]:=g[0];
      t:=cost[i];
      cost[i]:=cost[j];
      cost[j]:=t;
      t:=from[i];
      from[i]:=from[j];
      from[j]:=t;
      inc(i);
      dec(j);
    end;
  end;
  if j>l then qsort(l, j);
  if i<r then qsort(i, t);
end;

function can(x: longint): boolean;
var
  i, j: longint;
  len1, len2: extended;
  sum: extended;
  co: extended;
  tt: extended;
  temp: Array[1..maxn] of extended;
begin
  for i:=1 to tot do begin
    sum:=0;
    len1:=0;
    len2:=0;
    for j:=1 to m do begin
      sum:=sum+g[x, j]*g[i, j];
      len1:=len1+g[x, j]*g[x, j];
      len2:=len2+g[kk[i], j]*g[kk[i], j];
    end;
    len1:=sqrt(len1);
    len2:=sqrt(len2);
    if abs(len1)<=zero then
      exit(false);
    co:=sum/len1/len2;
    tt:=len1*co;
    for j:=1 to m do
      temp[j]:=g[kk[i], j]*tt/len2;
    for j:=1 to m do
      g[x, j]:=g[x, j]-temp[j];
  end;
  for j:=1 to m do
    if abs(g[x, j])>zero then
      exit(true);
  exit(false);
end;

procedure solve;
var
  i: longint;
begin
  qsort(1, n);
  tot:=1;
  num[1]:=from[1];
  ans:=ans+cost[1];
  kk[1]:=1;
  for i:=2 to n do
    if can(i) then begin
      inc(tot);
      kk[tot]:=i;
      num[tot]:=from[i];
      ans:=ans+cost[i];
      if tot=m then
        exit;
    end;
end;

procedure print;
var
  i, j: longint;
  t: longint;
begin
  if tot<m then
    writeln(0)
  else begin
    writeln(ans);
    for i:=1 to m do
      for j:=i+1 to m do
        if num[i]>num[j] then begin
          t:=num[i];
          num[i]:=num[j];
          num[j]:=t;
        end;
    for i:=1 to m do
      writeln(num[i]);
  end;
end;

begin
  init;
  solve;
  print;
end.

try test:
11 10
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
1
1
1
1
1
1
1
1
1
1
1

Out:
10
1
2
3
4
5
6
7
8
9
10

Edited by author 17.07.2010 23:05

n = 2
i = d = 0
j = 1

a:
1 1
1 1

First result:
1 1
0 0

Second result:
1 1
0 1

I've got AC. The tests are very difficult. REMEMBER: The epsilon should be very small!!!

You can use gauss over prime modular ring instead of long arithmetics
Just select lucky module =)

Because better use integer- Gauss solution without
heuristics.

i get WA#9 too. i don't know what is wrong is my programme.

I am also get wa on Test #9,can anybody give me any hints?
thx

Edited by author 22.03.2007 13:52

Yes, "lexicographic" has its usual meaning.

You may add as many new tests as you want, but you must not change the TL. When I solved the problem 4 years ago my program was fast enough and now it is TLE. How could I imagine someone will decide to decrease the TL? Why should I solve the problem which had been already solved?

Any hint about the "tricky tests" ?
I think I need help, thx

Omg.. My solution had silly mistake in Gauss method ('*' instead of '/'). And this solution got AC before rejudging.
i'm shocked...

I don't know either!

The problem is that if vector x is linear independent with vectors a
and b separately, that doesnt mean that x is linear independent with
vectors a, b. Example:
a = 1 5 3
b = 3 1 2

x = 4 6 5 = a+b (it is linear dependent with vectors a and b)

> [code was deleted]
>

Edited by moderator 22.04.2004 00:52

Vectors x1,...   xn are linery dependent iff
there exist numbers  a1,...an such that a1^2 + ... + an^2 !
= 0
and a1*x1+a2*x2 .... + an*xn = 0

Vectors are independent otherwise.

Vectors v1,v2,...,vn are linearly independent iff for any vi, you CAN'T find a set of real numbers (a1,a2,...,a(i-1),a(i+1),...,an) such that vi=a1*v1+a2*v2+...+a(i-1)*v(i-1)+a(i+1)*v(i+1)+...+an*vn.
That means for any n-dimensional vector v, you CAN find a set of real numbers (a1,a2...an) such that v=a1*v1+a2*v2+...+an*vn.

> Thanks.
> 71222119
> mailto : trungduck@yahoo.com
/////////////////////////
(0,0,0) will never be independent to any vector