# Poj Solution 1615

```http://poj.org/problem?id=1615

#include"iostream"
#include"stdlib.h"
#include"memory.h"
//#include"time.h"
using namespace std;

///////////////////////////
long cas;
///////////////////////////

void init()
{
n=5;total=0;
int i,j;
for(i=0;i<n;i++)
{
len[i]=80;
for(j=0;j<len[i];j++)
{
m[i][j]=rand()%201-100;
total+=m[i][j];
}
}
}

void init1()
{
n=0;total=0;
do
{
len[n]=0;
do
{
cin>>m[n][len[n]++];
total+=m[n][len[n]-1];
}
while(m[n][len[n]-1]!=9999&&m[n][len[n]-1]!=-9999);

total-=m[n][len[n]-1];
len[n]--;
n++;
}while(m[n-1][len[n-1]]!=-9999);

}

int a[5];long next;int prev[520];

void find(long sum,long max,int rest)
{
int i;long sa,sb;

if(rest==0)
{
return;
}

for(i=0;i<n;i++)
if(a[i]<len[i])
{
if(prev[rest]>=0&&prev[rest]!=i)
{
sa=m[prev[rest]][a[prev[rest]]-2];
if(m[prev[rest]][a[prev[rest]]-1]+m[i][a[i]]>0)sa+=m[prev[rest]][a[prev[rest]]-1]+m[i][a[i]];

sb=m[i][a[i]];
if(m[i][a[i]+1]+m[prev[rest]][a[prev[rest]]-2]>0)sb+=m[i][a[i]+1]+m[prev[rest]][a[prev[rest]]-2];

if(sa>sb)continue;
}

a[i]+=2;
sum+=m[i][a[i]-2];
prev[rest-2]=i;
find(sum+m[i][a[i]-1],sum>max?sum:max,rest-2);
sum-=m[i][a[i]-2];
a[i]-=2;
}
return ;
}

void yasuo()
{
int i,j,k;
for(i=0;i<n;i++)
{
for(j=1,k=0;j<len[i];j++)
{
if(m[i][j]==0)continue;
if((m[i][j]>=0&&m[i][k]>=0)||(m[i][j]<=0&&m[i][k]<=0))m[i][k]+=m[i][j];
else
{
k++;
m[i][k]=m[i][j];
}
}

len[i]=k+1;

if(m[i][k]>0)m[i][len[i]++]=0;
m[i][len[i]]=-9999;
}
return ;
}

int main()
{
int t,i,st;long sum;
cin>>t;
while(t--)
{
init1();
//init();

yasuo();

sum=0;st=0;
for(i=0;i<n;i++)
{
a[i]=0;
if(m[i][0]<=0)
{
a[i]++;
sum+=m[i][0];
}
st+=len[i]-a[i];
}