// Weighted interval scheduling.  See Kleinberg & Tardos, chapter 6

// Finds solution using powerset enumeration. 10/08/11 BPW

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

#define TABSIZE (31) // Due to powerset size

int n,s[TABSIZE],f[TABSIZE],v[TABSIZE],p[TABSIZE];
char subset[TABSIZE],subsetKeep[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,sumKeep;

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);
}

// p values are used to make overlap test simple.
for (i=1;i<=n;i++)
  p[i]=binSearchLast(f,n+1,s[i]);

// Start at empty set for powerset enumeration
for (i=1;i<=n+1;i++)
  subset[i]=subsetKeep[i]=0;

sum=sumKeep=0;
while (1)
{
  // Move to next subset using binary increment technique.
  // Complement the low-order ones and remove elements from next subset.
  for (i=1;subset[i];i++)
  {
    sum-=v[i];
    subset[i]=0;
  }
  if (i==n+1)  // All subsets enumerated?
    break;

  // Put new first (e.g. low-order one) element into the next subset.
  sum+=v[i];
  subset[i]=1;

  // Assure that adjacent intervals do not overlap
  for (j=i+1;j<=n;j++)
    if (subset[j])  // Found adjacent interval
    {
      if (i<=p[j])  // No overlap
        i=j;        // Move over to check next pair
      else
        break;      // This subset has overlap for intervals i & j
    }

  if (j>n && sum>sumKeep)  // No overlap and improvement
  {
    printf("Improvement to %d\n",sum);
    sumKeep=sum;
    for (i=1;i<=n;i++)
      subsetKeep[i]=subset[i];
  }
}

printf("  i   s   f   v   p include\n");
for (i=1;i<=n;i++)
{
  printf("%3d %3d %3d %3d %3d",i,s[i],f[i],v[i],p[i]);
  if (subsetKeep[i])
    printf("    *");
  printf("\n");
}

printf("sum is %d\n",sumKeep);
}