// Weighted interval scheduling for two rooms.  BPW 2/10/10
// See Kleinberg & Tardos, chapter 6 for one room

// Lab 2, Summer 2012

// This version handles M[i][i] differently.  2/17/13

#include <stdio.h>
#include <stdlib.h>

#define TABSIZE (100)

//#define LAB2SUM12

int n,s[TABSIZE],f[TABSIZE],v[TABSIZE],p[TABSIZE],M[TABSIZE][TABSIZE],
    room1[TABSIZE],room2[TABSIZE];

int max(int x,int y)
{
if (x>y)
  return x;
return y;
}

int binSearchLast(int *a,int n,int key)
{
// Input: int array a[] with n elements in ascending order.
//        int key to find.
// Output: Returns subscript of the last a element <= key.
//         Returns -1 if key<a[0].
// Processing: Binary search.
  int low,high,mid;
  low=0;
  high=n-1;
// subscripts between low and high are in search range.
// size of range halves in each iteration.
// When low>high, low==high+1 and a[high]<=key and a[low]>key.
  while (low<=high)
  {
    mid=(low+high)/2;
    if (a[mid]<=key)
      low=mid+1;
    else
      high=mid-1;
  }
  return high;
}

int main()
{
int i,j,sum=0,r1Count=0,r2Count=0;

scanf("%d",&n);
f[0]=(-999999); // For binarySearchLast
for (i=1;i<=n;i++)
  scanf("%d %d %d",&s[i],&f[i],&v[i]);
for (i=2;i<=n && f[i-1]<=f[i];i++)
  ;
if (i<=n)
{
  printf("Intervals not ordered by finish time %d\n",__LINE__);
  exit(0);
}

// Determine rightmost preceding interval.
for (i=1;i<=n;i++)
  p[i]=binSearchLast(f,n+1,s[i]);

// Echo input
#ifdef LAB2SUM12
printf("%d\n",n);
for (i=1;i<=n;i++)
  printf("%d %d %d\n",s[i],f[i],v[i]);
#else
printf("  i   s   f   v   p\n");
for (i=1;i<=n;i++)
  printf("%3d %3d %3d %3d %3d\n",i,s[i],f[i],v[i],p[i]);
#endif

// Dynamic programming cost computation
// M[i][j] is the max revenue that can be achieved using intervals
// from 1..i for room 1 and from 1..j for room 2 where an interval
// may only be assigned to one room.
for (i=0;i<=n;i++)
  for (j=0;j<=n;j++)
    M[i][j]=
      (i==j) ?
        (i==0) ? 
           0 // Base case
        :
           M[i][i-1] // simplified handling
      :
        (i>j) ?
           max(M[p[i]][j]+v[i],
               M[i-1][j])
        :  // i<j
           max(M[i][p[j]]+v[j],
               M[i][j-1])
      ;

#ifndef LAB2SUM12
// DP result
printf(" M ");
for (i=0;i<=n;i++)
  printf(" %3d",i);
printf("\n");
for (i=0;i<=n;i++)
{
  printf("%3d",i);
  for (j=0;j<=n;j++)
    printf(" %3d",M[i][j]);
  printf("\n");
}
#endif

// Traceback
i=j=n;
while (1)
{
  //printf("Trace at M[%d][%d]\n",i,j);
  if (i==j)
    if (i==0)
      break;
    else
      j--; // simplified handling
  else if (i>j)
    if (M[i][j]==M[p[i]][j]+v[i])
    {
      //printf("Room one gets interval %d\n",i);
      room1[r1Count++]=i;
      sum+=v[i];
      i=p[i];
    }
    else
      i--;
  else // i<j
    if (M[i][j]==M[i][p[j]]+v[j])
    {
      //printf("Room two gets interval %d\n",j);
      room2[r2Count++]=j;
      sum+=v[j];
      j=p[j];
    }
    else
      j--;
}
// Lab 2 Summer 2012 output
#ifdef LAB2SUM12
printf("%d\n",r1Count);
for (i=r1Count-1;i>=0;i--)
  printf("%d %d %d\n",s[room1[i]],f[room1[i]],v[room1[i]]);
printf("%d\n",r2Count);
for (i=r2Count-1;i>=0;i--)
  printf("%d %d %d\n",s[room2[i]],f[room2[i]],v[room2[i]]);
printf("%d\n",sum);
#else
printf("%d\n",r1Count);
for (i=r1Count-1;i>=0;i--)
  printf("(%d) %d %d %d\n",room1[i],s[room1[i]],f[room1[i]],v[room1[i]]);
printf("%d\n",r2Count);
for (i=r2Count-1;i>=0;i--)
  printf("(%d) %d %d %d\n",room2[i],s[room2[i]],f[room2[i]],v[room2[i]]);
printf("%d\n",sum);
#endif
}