Problema A - Nova Ioiorque

Há quem olhe para as cidades como frias e disformes selvas de betão, onde torres de cimento se erguem, formando uma aberração cinzenta com várias megatoneladas. No entanto, há também quem veja nas cidades verdadeiras obras de arte, onde os prédios rasgam o céu e formam as comummente denominadas skylines. Uma skyline é uma fila de prédios, com alturas e belezas variáveis e que geralmente é observada de fora da fila, de modo a ser possível ver todos os prédios ao mesmo tempo.

Todavia, em Nova Ioiorque, não é assim que se olha para esta paisagem urbana. Nessa cidade, há N prédios, o i-ésimo com uma altura hi inteira positiva, colocados em fila entre as posições 1 e N, e costumam ser observados de um ponto turístico localizado na posição 0, e de onde só é possível ver o prédio que ocupa a posição i se este for mais alto do que todos os prédios nas posições 1, 2, ..., i-1. Adicionalmente, cada prédio tem uma certa beleza wi, um valor inteiro, e dizemos que a beleza da vista a partir do ponto turístico é a soma das belezas dos prédios visíveis.

Vejamos um exemplo: suponhamos que N=6 e temos que os prédios têm alturas h = [2, 1, 6, 2, 3, 4] e belezas w = [3, 2, 10, 5, 6, 6], como mostra a imagem seguinte:

Skyline

Um observador na posição 0 consegue então ver os prédios 1 (altura 2) e 3 (altura 6) e por isso a beleza desta skyline é de 3 + 10 = 13.

A Organização Niveladora de Imobiliário está interessada em aumentar a beleza desta paisagem. De modo a alcançarem o objetivo, pretendem demolir alguns dos prédios. Contudo, demolir prédios afeta negativamente a beleza de Nova Ioiorque, dependendo de cada um dos prédios demolidos. Cada prédio tem um valor de fealdade dos seus destroços (inteiro não negativo) ci, que significa que ao demolir o prédio i os seus destroços contribuem negativamente um valor de ci para beleza da skyline.

A Organização Niveladora de Imobiliário tem à sua disposição toda a dinamite possivelmente necessária para demolir todos os prédios de Nova Ioiorque e pretende determinar a beleza máxima que consegue alcançar, ou seja, a soma das belezas dos prédios visíveis a partir do ponto turístico (após realizar as demolições) menos a soma das fealdades dos destroços criados.

Para o exemplo anterior, vamos supor que os prédios têm as seguintes fealdades quando demolidos c = [10, 2, 1, 1, 4, 3]. Então a solução ótima seria demolir os seguintes prédios, para obter uma beleza de 14 (os prédios 1, 5 e 6 passam a estar na skyline com soma de belezas igual a 15 e os destroços do prédio 3 contribuem negativamente em uma unidade de fealdade):

Skyline

Assim sendo, a tua tarefa é determinar a beleza máxima da skyline de Nova Ioiorque!

O Problema

Dado um inteiro positivo N, representando o número de prédios, e para cada um a sua altura (inteira positiva) hi, beleza (inteira) wi e a fealdade dos seus destroços (inteiro não negativo) ci, procuramos saber a beleza máxima da skyline de Nova Ioiorque.

Input

A primeira linha contém um inteiro N, representando o número de prédios.

Seguem-se N linhas, cada uma contendo 3 inteiros separados por espaços: altura hi, beleza wi e a fealdade dos seus destroços ci.

Output

Um inteiro representando a beleza máxima da skyline de Nova Ioiorque após possíveis demolições.

Nota: o valor da beleza máxima pode exceder 232.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ N ≤ 1 000 Número de prédios
1 ≤ hi ≤ 100 000 000 Alturas de cada prédio
-100 000 000 ≤ wi ≤ 100 000 000 Beleza de cada prédio
0 ≤ ci ≤ 100 000 000 Fealdade de demolição

Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:

Grupo Número de Pontos Restrições adicionais
1 20 N ≤ 10
2 20 As alturas dos prédios estão por ordem crescente
3 25 As fealdades de demolição são todas 0 (ci = 0)
4 35 -

Input do Exemplo 1

6
2 3 10
1 2 2
6 10 1
2 5 1
3 6 4
4 6 3

Output do Exemplo 1

14

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

5
1 2 1
2 2 3
3 -6 7
4 -5 4
5 2 2

Output do Exemplo 2

-4

Input do Exemplo 3

5
5 5 0
6 3 0
3 2 0
4 3 0
5 4 0

Output do Exemplo 3

9

Prova de Seleção para as IOI'2019
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(9 de Junho de 2019)