/* KSP 14-1-1
 * Kostky
 *
 * Petr Baudis
 * Rocnik: 2
 * Skola: Ad Fontes
 */


/*
 * Vstup: N\n - pocet kostek, dale N-krat: <X>x<Y>x<Z>
 *
 * Vystup: M\n - maximalni vyska veze postavene z kostek tak, ze kostka vzdy
 * stoji celou svou podstavou na kostce pod ni
 *
 * Algoritmus:
 * 
 * Nactene kostky se prubezne ukladaji do stromu, z jehoz kazdeho uzlu (kostky)
 * muze vest libovolny pocet vetvi, kazda ke kostce mensi nebo stejne jako
 * kostka, odkud vetev vede.
 *
 * U kazde vetve si dale urcujeme jeji hodnotu - nejvyssi potencialni vysku
 * jejich potomku. Ziskame ji souctem vysky dcerine kostky a hodnoty nejlepsi
 * vetve, ktera z ni vychazi.
 * 
 * Jakmile dostaneme na vstupu kostku, projdeme cely strom tak, az najdeme
 * vhodne misto, kam ji vlozit - tedy pokud dojdeme ke kostce, jejiz dcerine
 * kostky maji vsechny alespon jeden rozmer mensi nez vstupni kostka, pripadne
 * samozrejme pokud tam zadne dcerine kostky uz nejsou. Techto kostek
 * samozrejme muze byt vic, v tom pripade dale postupujeme pro kazdou zvlast.
 *
 * Tehdy tedy vytvorime z kostky novou vetev, vedouci ke vstupni kostce, nacez
 * projdeme vsechny sourozenecke kostky, a ty, ktere se pod nas vejdou,
 * presuneme na jejich nove pusobiste (pri tom upravime hodnoty vetvi, jak je
 * popsano nize). Nacez projdeme vsechny potomky zbylych sourozeneckych kostek,
 * a kostky, ktere se pod nas vejdou, si pod nas prilinkujeme (pricemz je ovsem
 * ponechame i v jejich puvodni lokaci). Jejich potomky uz se prirozene
 * nezabyvame, protoze ty se presouvaji zaroven s kostkami samymi.
 *
 * Nyni spocitame hodnotu vsech nasich vetvi, nacez projdeme postupne odzdola
 * vsechny nadrazene kostky, pro kazdou spocitame hodnotu vetve vedouci smerem
 * k nam, a pokud se stane nejlepsi vetvi, pokracujeme v nasi ceste vzhuru.
 *
 * Po vlozeni posledni kostky jiz pouze vybereme tu vetev vedouci z nejvetsi
 * kostky, ktera ma nejvyssi hodnotu, a tuto hodnotu vypiseme.
 *
 * Kazda kostka je v celem stromu pouze jednou, avsak muze k ni vest vice vetvi
 * z ruznych mist stromu, pro ktere je tato kostka i vsichni jeji potomci
 * spolecna. Diky tomu se pouzije pouze tolik pameti, kolik kostek skutecne je,
 * plus vsak urcite misto pro zaznamenani vzajemnych vazeb kostek... pametova
 * narocnost by se tedy dala zrejme zjednodusene vyjadrit jako O(N).
 *
 * Algoritmus je efektivnejsi pro mensi pocet stejnorodejsich kostek, pri
 * velkem poctu kostek by bylo asi lepsi spocitat hodnoty jednotlivych vlaken
 * jednorazove, doufame vsak, ze Frantikuv tatinek neni multimilionar, tedy je
 * kostek rozumny pocet :-). Pri pridani kazde kostky potrebujeme cas zejmena
 * na prohledani stromu a nalezeni vhodnych umisteni kostky (tedy v prumeru
 * neco jako 2^(N/2), protoze vetsinou budeme prohledavat jenom urcitou cast
 * stromu, a ze to bude prumerne polovina stromu zni jako rozumny predpoklad),
 * dale prohledani sourozencu a prelinkovani tech mensich (zanedbatelne), pote
 * prohledani zbylych sourozencu a nalezeni nejvetsich mensich nez nase kostka
 * (narocnejsi, ale presto neprilis vyznamne), a nakonec prepocitani vsech
 * rodicu, coz je ovsem take relativne zanedbatelne... Casova narocnost je tedy
 * v extremnim pripade zhruba O(2^N).
 *
 * Narocnosti urcuji poprve v zivote, takze je mozne ze jsem to pochopil
 * spatne... :-) 
 */


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


/*
 * 
 * Typy
 * 
 */


typedef struct CUBE_T {
  int x, y, z;

  int value; /* z + branch[nejlepsi]->z */

  int id;
  
  int branches;
  struct CUBE_T **branch;

  int roots;
  struct CUBE_T **root;
} cube_t;

cube_t *cube = NULL; /* prvni kostka */


/*
 * 
 * Alokace pameti
 * 
 */


void *
memalloc(size_t len) {
  void *p = malloc(len);

  if (! p && len) {
    fprintf(stderr, "NE (%d)\n", len);
    exit(2);
  }

  return p;
}

void *
memrealloc(void *op, size_t len) {
  void *p = op?realloc(op, len):malloc(len);

  if (! p && len) {
    fprintf(stderr, "NE (%d)\n", len);
    exit(3);
  }

  return p;
}



/* 
 *
 * Operace s mnozinou kostek
 *
 */


void
sum(int *len1, cube_t ***set1, int len2, cube_t **set2) {
  int c, d;
  
  *set1 = memrealloc(*set1, (*len1 + len2) * sizeof(cube_t *));
  
  /* vyhazet duplicity */
  for (c = 0; c < len2; c++) {
    int hits = 0;
    
    for (d = 0; d < *len1; d++)
      if (set2[c]->id == (*set1)[d]->id) {
	hits++;
	break;
      }

    if (! hits) {
      (*set1)[*len1] = set2[c];
      (*len1)++;
    }
  }
  
  *set1 = memrealloc(*set1, *len1 * sizeof(cube_t *));
}

void
add(int *len, cube_t ***set, cube_t *new) {
  int c, hits = 0;
  
  (*len)++;
  *set = memrealloc(*set, *len * sizeof(cube_t *));
  
  /* vyhazet duplicity */
  for (c = 0; c < *len - 1; c++)
    if ((*set)[c]->id == new->id) {
      hits++;
      break;
    }

  if (! hits) {
    (*set)[*len - 1] = new;
  } else
    (*len)--; /* XXX: maly leak, ale na druhou stranu bude budouci
	       * realokace trochu rychlejsi */
}

void
del(int *len, cube_t ***set, int idx) {
  if (idx >= *len)
    return;

  (*len)--;
  
  memmove(*set + idx, *set + idx + 1, (*len - idx) * sizeof(cube_t *));
  
  *set = memrealloc(*set, *len * sizeof(cube_t *));
}



/*
 *
 * Operace s kostkou
 *
 */


cube_t *
newcube(int id) {
  cube_t *c;

  c = memalloc(sizeof(cube_t));

  c->x = c->y = c->z = 0;
  c->value = 0;
  c->id = id;
  c->branches = 0;
  c->branch = NULL;
  c->roots = 0;
  c->root = NULL;

  return c;
}

/* Najdi kostky co nejpodobnejsi vzoru, ne vsak mensi nez on */
/* Vracime pouze unikatni kostky, i kdyz se v stromu vyskytuji
 * nekolikrat, budou v matches pouze jednou. */
/* Vrati pocet vyhovujicich kostek */
int
findbigger(cube_t *root, cube_t *pattern, cube_t ***matches) {
  int b;
  int hits = 0;
  int mn = 0; /* matches number */

  *matches = NULL;
  
  for (b = 0; b < root->branches; b++)
    if (root->branch[b]->x >= pattern->x &&
	root->branch[b]->y >= pattern->y) {
      cube_t **lmatches;
      int lmn;
      
      lmn = findbigger(root->branch[b], pattern, &lmatches);
      sum(&mn, matches, lmn, lmatches);
      if (lmn) free(lmatches);
      
      hits++;
    }
  
  if (! hits) /* dal uz to nejde, takze jsem to ja */
    add(&mn, matches, root);
  
  return mn;
}

/* Najdi nejblizsi kostky co nejpodobnejsi vzoru a mensi nez on */
int
findsmaller(cube_t *root, cube_t *pattern, cube_t ***matches) {
  int b;
  int mn = 0; /* matches number */

  *matches = NULL;
  
  for (b = 0; b < root->branches; b++)
    if (root->branch[b]->x <= pattern->x &&
	root->branch[b]->y <= pattern->y)
      add(&mn, matches, root->branch[b]);
    else {
      cube_t **lmatches;
      int lmn;
      
      lmn = findsmaller(root->branch[b], pattern, &lmatches);
      sum(&mn, matches, lmn, lmatches);
      if (lmn) free(lmatches);
    }
  
  return mn;
}

/* Spocitej hodnotu (nejvyssi potencialni vysku) uzlu */
/* Vrati 1 pokud se hodnota zmenila, jinak 0 */
int
compute(cube_t *node) {
  int oldval = node->value;
  int maxval = 0;
  int nc;

  node->value = node->z;

  for (nc = 0; nc < node->branches; nc++)
    if (node->branch[nc]->value > maxval)
      maxval = node->branch[nc]->value;

  node->value += maxval;

  return ! (oldval == node->value);
}

/* Aktualizuj hodnoty uzlu vedoucich do daneho uzlu */
void
recompute(cube_t *node) {
  int nc;

  if (compute(node))
    for (nc = 0; nc < node->roots; nc++)
      recompute(node->root[nc]);
}


/*
 *
 * Vlastni program
 *
 */


int
main() {
  char inb[128];
  int cubes;
  int c;
  cube_t *acube = NULL; /* aktualni kostka */

  fgets(inb, 128, stdin);
  cubes = atoi(inb);
  if (! cubes) {
    fprintf(stderr, "NE\n");
    exit(1);
  }

  cube = newcube(cubes);
  cube->x = cube->y = INT_MAX; /* podlaha ;-) */
  cube->z = 0;
 
  for (c = 0; c < cubes; c++) {
    cube_t **cubes;
    int cube_no;
    int nc;
    
    acube = newcube(c);

    scanf("%dx%dx%d", &acube->x, &acube->y, &acube->z);
    
    /* nejlepsi kostky */
    cube_no = findbigger(cube, acube, &cubes);
      
    for (nc = 0; nc < cube_no; nc++) {
      cube_t *wcube = cubes[nc];
      int ncs; /* s == sibling == sourozenec ;-) */
      int need_recompute = 0;
      
      /* pridej kostku k rodicovi */
      add(&wcube->branches, &wcube->branch, acube);
      add(&acube->roots, &acube->root, wcube);

      /* prohledej sourozence */
      for (ncs = 0; ncs < wcube->branches; ncs++) {
	cube_t *wwcube = wcube->branch[ncs];

	/* sebe neres */
	if (wwcube->id == acube->id)
	  continue;
	
	/* mensi prElinkuj */
	if (wwcube->x <= acube->x &&
	    wwcube->y <= acube->y) {
	  int ncss;

	  /* prohledej jeho koreny a vyhod onoho sourozence */
	  for (ncss = 0; ncss < wwcube->roots; ncss++) {
	    if (wwcube->root[ncss]->id == wcube->id) {
	      del(&wwcube->roots, &wwcube->root, ncss);
	      break;
	    }
	  }
	  del(&wcube->branches, &wcube->branch, ncs);

	  add(&acube->branches, &acube->branch, wwcube);
	  add(&wwcube->roots, &wwcube->root, acube);

	  need_recompute++;
	}
      }

      /* vetsi prohledej a mensi prIlinkuj */
      {
	cube_t **cubess;
	int cube_nos;
	int ncss;

	cube_nos = findsmaller(wcube, acube, &cubess);

	for (ncss = 0; ncss < cube_nos; ncss++)
	  if (cubess[ncss]->id != acube->id) {
	    add(&acube->branches, &acube->branch, cubess[ncss]);
	    add(&cubess[ncss]->roots, &cubess[ncss]->root, acube);
	  }
	
	if (cube_nos) free(cubess);
      }

      /* pokud jsme zmenili jeho vetev, prepocitej ho */
      if (need_recompute)
	compute(wcube);
    }
    
    /* spocitej hodnotu nasich vetvi a pak prip. prepocitej vyssi */
    recompute(acube);

    if (cube_no) free(cubes);
  }
  
  compute(cube);
  printf("%d\n", cube->value);
  
  return 0;
}