uva 473 - Raucous Rockers

/*
Problem link
Type: DP
Algorithm:
 Let f(i,j,k) be the largest amount of songs from 1 to k can be written into 
 the disks from 1 to i with disk i having space j
 There are 3 cases:
  j = 0: This mean disk i has space of 0, hence it cannot carry any song, there for
  f(i,j,k) for this case is f(i-1,t,k), that is, the number of songs were written in 
  the previous i-1 disk. Of course the previous disks can carry song k since the
  current disk doesnt have any space to carry it.
  
  a[k]<=j: The space of disk i is enough to carry the song k. There are two choices
  for us now: choose k or not choose k. If we choose song k, f(i,j,k) is equal to
  f(i,j-a[k],k-1)+1. That is, before we choose k, the space is j-a[k], and the set of 
  songs is 1 to k-1 because we cannot choose k twice. If we dont choose song k, 
  f(i,j,k) is equal to f(i,j,k-1). That is, if we dont choose song k, the space is still j,
  and the set of song is 1 to k-1 excluding song k. Hence:
   f(i,j,k) = max(f(i,j-a[k],k-1)+1,f(i,j,k-1)) for a[k]<=j;
  
  a[k]>j: The space of disk i is not enough to carry song k. There are two cases now:
  If before k there are no songs has been chosen for disk i, this mean f(i,j,k) now is
  f(i-1,t,k), now there are only songs that were chosen in the previous disks.
  If there are songs that has been chosen for disk i, this mean f(i,j,k) now is
  f(i,j,k-1), that is, the set of songs now is only from 1 to k-1. Hence:
   f(i,j,k) = max(f(i-1,t,k),f(i,j,k-1)) for a[k]>j;
 So we have complete our DP algorithm, the next tricky thing is the bound of n, m, t. 
 I think they are quiet large so I give them 10000, 200, 200. This takes quiet a lot of
 memory space. Maybe we can use the space saving trick to fix this, 2 matrixs of (t*m)
 size is ok since we only consider the number of songs to the previous disk only. The complexity
 is O(n*m*t). 
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 600;
//-----------------------------
int a[10241];
int f[200][200][10241];
int n,m,t;
//-----------------------------
int solve();
//-----------------------------
int main() {
 int ntest;
 cin >> ntest;
 for (int test=1; test<=ntest; test++)
 {
  if (test>1) cout << endl;
  cin >> n >> t >> m;
  string num;
  int value;
  for (int i=1; i<=n; i++)
  {
   cin >> num;
   value = 0;
   for (int j=0; j<num.length(); j++) 
    if (num[j]>='0' && num[j]<='9') value = value*10+int(num[j])-48;
   a[i] = value;
  }
  cout << solve() << endl;
 }
 return 0;
}
//-----------------------------
int solve() {
 for (int i=0; i<=m; i++)
  for (int j=0; j<=t; j++)
   for (int k=0; k<=n; k++) f[i][j][k] = 0;
 for (int i=1; i<=m; i++)
  for (int j=0; j<=t; j++)
   for (int k=1; k<=n; k++)
    if (j==0) f[i][j][k] = f[i-1][t][k];
    else if (a[k]<=j) f[i][j][k] = max(f[i][j][k-1],f[i][j-a[k]][k-1]+1);
    else if (a[k]>j) f[i][j][k] = max(f[i-1][t][k],f[i][j][k-1]);
 return(f[m][t][n]); 
}
//-----------------------------