Došla je sezona vašara. Trgovac Vasa bi da ove sezone zaradi dosta para pa hoće da sve isplanira unapred.

U više gradova se organizuju vašari. Vasa zna kog dana u nekom gradu počinje vašar i koliko dana traje. Isto tako zna kolika će gužva biti na tom vašaru i koliko može da zaradi u jednom danu.

Ali Vasa ne planira da prodaje samo u jednom gradu. On planira da se seli iz jednog grada u drugi i želi da mu mi odredimo koliko najviše može da zaradi.

Ulaz.

(Ulazni podaci se nalaze u datoteci vasari.in) U prvom redu se nalaze dva broja n i p (1 ≤ p ≤ n ≤ 1000). Broj n predstavlja broj gradova u kojima se održavaju vašari, a p je redni broj grada u kojem se Vasa nalazi prvog dana. U svakom od sledećih n redova (svaki red je vezan za jedan grad) se nalaze po n + 3 broja: a, b, c, v[1], v[2], ..., v[n] (1 ≤ a, b ≤ 200, 1 ≤ c ≤ 1000, 0 ≤ v[i] ≤ 400). Broj a predstavlja kog dana u tom gradu počinje vašar, b predstavlja koliko dana traje, c predstavlja koliko Vasa može da zaradi u jednom danu na tom vašaru. Broj v[i] predstavlja koliko je potrebno dana da Vasa pređe iz tog grada u grad i. Primetite da godina može imati i više od 365 dana (ali ne više od 400 dana).

Izlaz.

(Izlazne podatke upisati u datoteku vasari.out) Treba da se sastoji od samo jednog broja koji predstavlja koliko Vasa može da zaradi.

Primer 1.

3 2
5 6 5 0 3 3
1 5 2 2 0 1
7 8 3 1 2 0

37

Objašnjenje.

Prva dva dana Vasa prodaje u drugom gradu i zaradi 4. Onda dva dana ne prodaje nego se seli u prvi grad. Tamo prodaje tokom celog vašara i zaradi 30. Onda tri dana prelazi u treći grad i u njemu prodaje samo jedan dan, i zaradi 3. Ukupno je zaradio 4 + 30 + 3 = 37.

#include <stdio.h>
#include <malloc.h>

int main()
{
  long i,j,d,p;
  int n,st;
  int  poc[1005],duz[1005],z[1005];
  int *mat[1005];
  int x;
  long *res[1005];
  long max=0;
  freopen("vasari.in","r",stdin);
  freopen("vasari.out","w",stdout);
  scanf("%d%d",&n,&st);
  st--;
  for(i=0;i<n;i++)
  {
    scanf("%d%d%d",&poc[i],&duz[i],&z[i]);
    if(poc[i]+duz[i]>max)
      max=poc[i]+duz[i];
    mat[i]=(int*)malloc(1005* sizeof(int));
    res[i]=(long*)malloc(505*sizeof(long));
    for(j=0;j<n;j++)
    {
      scanf("%d",&mat[i][j]);
    }
  }
  for(i=0;i<n;i++)
  {
    res[i][0]=-1;
  }
  res[st][0]=0;
  for(d=1;d<=max;d++)
  {
    for(i=0;i<n;i++)
    {
      res[i][d]=res[i][d-1];
      if(res[i][d]>=0 && d>=poc[i] && d<poc[i]+duz[i])
  res[i][d]+=z[i];
      for(j=0;j<n;j++)
      {
  if(i==j) continue;
  p=d-mat[j][i];
  if(p<0 || res[j][p]==-1) continue;
  if(res[j][p]>res[i][d])
    res[i][d]=res[j][p];
      }
    }
  }

  d=0;
  for(i=0;i<n;i++)
  {
    if(res[i][max]>d)
      d=res[i][max];
  }
  printf("%d\n",d);

  return 0;
}