시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Festivais de música deveriam ser pura diversão, porém alguns deles se tornam tão grandes a ponto de causar dor de cabeça para os frequentadores. O problema é que são tantas atrações boas tocando em tantos palcos que a simples tarefa de escolher quais shows assistir se torna complexa.

Para ajudar frequentadores de tais festivais, Fulano decidiu criar um aplicativo que, após avaliar as músicas ouvidas em seus serviços de streaming favoritos, sugere quais shows assistir de modo que não exista outra combinação de shows melhor de acordo com os critérios descritos a seguir:

  • Para aproveitar a experiência ao máximo é importante assistir cada um dos shows escolhidos por completo;
  • Ir no festival e não ver um dos palcos está fora de cogitação;
  • Para garantir que a seleção dos artistas seja compatível com o usuário, contou-se quantas músicas de cada artista o usuário conhece por já ter ouvido-as nos serviços de streaming. O total de músicas conhecidas dos artistas escolhidos deve ser o maior possível.

Infelizmente a versão beta do aplicativo recebeu várias críticas, pois os usuários conseguiram pensar em seleções melhores que aquelas sugeridas. Sua tarefa nesse problema é ajudar Fulano e escrever um programa que, dadas as descrições dos shows acontecendo em cada palco, calcula a lista ideal para o usuário.

O tempo de deslocamento entre os palcos é ignorado; portanto, desde que não haja interseção entre os horários de quaisquer dois shows escolhidos considera-se que é possível assistir a todos por completo. Em particular, se um show acaba exatamente quando um outro começa, é possível assistir a ambos.

입력

A primeira linha contém um número inteiro 1 ≤ N ≤ 10 representando o número de palcos. As N linhas seguintes descrevem os shows acontecendo em cada palco. A i-ésima delas é composta por um inteiro Mi ≥ 1, representando o número de shows marcados para o i-ésimo palco seguido por Mi descrições de shows. Cada descrição de show contém 3 inteiros ij , fj e oj (1 ≤ ij < fj ≤ 86400 e 1 ≤ oj ≤ 1000), representando respectivamente os horários de início e fim do show e o número de músicas do cantor se apresentando que foram previamente ouvidas pelo usuário. A soma dos Mi não excederá 1000.

출력

Seu programa deve produzir uma única linha com um inteiro representando o total de músicas previamente ouvidas dos artistas escolhidos, ou −1 caso não haja solução válida.

예제 입력 1

3
4 1 10 100 20 30 90 40 50 95 80 100 90
1 40 50 13
2 9 29 231 30 40 525

예제 출력 1

859

예제 입력 2

3
2 13 17 99 18 19 99
2 13 14 99 15 20 99
2 13 15 99 18 20 99

예제 출력 2

-1