Problema B - Arranha-Céus

Todas as grandes cidades têm muitos arranha-céus. Vistas de longe, estas cidades apresentam panorâmicas dominadas por estes "gigantes", formando uma skyline muito característica de cada localidade.

Acabaste de descobrir um sítio absolutamente fantástico para tirar uma foto que capta bem toda esta realidade urbana. No entanto, o número de arranha-céus é tão grande que muitas vezes alguns edifícios se tapam uns aos outros e as fotos não mostram a totalidade dessas obras-primas arquitetónicas. Mesmo assim, tu queres saber quantos edifícios vão aparecer na foto, e quantos não vão aparecer, por estarem escondidos atrás de outros.

Para o efeito deste problema, uma foto pode ser assimilada a um quadriculado. A câmara municipal é muito rígida nos edifícios que autoriza e determinou que todos os arranha-céus podem ser descritos por meio de um retângulo que cobre parte do quadriculado. Por exemplo, os seguintes 5 diferentes edifícios são construções que existem na cidade e que podem ser vistos do ponto onde estás:

Em relação ao ponto de vista da foto, alguns edifícios estão mais perto e outros mais longe. Por exemplo, para a figura anteriormente mostrada, o edifício mais à esquerda é o que está mais "à frente". O segundo edifício a contar da esquerda está logo atrás desse primeiro edifício, mas à frente dos outros três edifícios, e por aí adiante. Deste modo, a vista obtida pela foto é a que a figura seguinte representa:

Nesta foto, o primeiro edifício aparece totalmente. O segundo edifício, embora parcialmente tapado, também aparece. O terceiro, no entanto, está completamente tapado pelos dois primeiros edifícios, e por isso não aparece na foto. Já o quarto e o quinto edifícios aparecem na foto, ainda que o último apenas parcialmente. Portanto, o número de arranha-céus que aparecem na foto é 4.

Para além disto, queres também perceber qual é a zona da foto com mais edifícios uns atrás dos outros. Por outras palavras, queres saber qual o máximo número de edifícios que ocupam uma mesma quadrícula. No caso da figura atrás descrita, este número é 3, porque existe uma zona da foto que engloba o primeiro, segundo e terceiro edifícios da foto, nomeadamente o retângulo entre as coordenadas (4,1) e (5,6).

Para um caso geral, consegues criar um programa que faça estes cálculos?

O Problema

Dadas as coordenadas inteiras 2D de uma sequência de arranha-céus retangulares, estando a sequência ordenada pela distância crescente em relação ao ponto de onde tiras a foto, a tua tarefa é calcular duas coisas. Primeiro, o número de arranha-céus que são visíveis, ou seja, que aparecem na foto (ainda que apenas parcialmente). Segundo o máximo número de arranha-céus que estão uns atrás dos outros, ou seja, o maior número de edifícios que estão numa mesma posição do quadriculado.

Input

Na primeira linha do input vem número inteiro N, indicando o número de arranha-céus a considerar.

Seguem-se exatamente N linhas, cada uma com três números inteiros "X1_i X2_i Y_i", separados por um espaço, indicando as coordenadas do i-ésimo arranha-céus (da coluna X1_i até à coluna X2_i, com altura Y_i).

A ordem em que os arranha-céus aparecem corresponde à ordem em que estes estão em relação à foto, sendo que o arranha-céus que vem na primeira linha está à frente de todos os outros edifícios.

O exemplo de input corresponde às figuras usadas no enunciado do problema.

Output

O output deve ser constituído por uma única linha contendo dois inteiros V e M, separados por um espaço. V deve indicar o número de arranha-céus visíveis na foto e M o máximo de arranha-ceús uns atrás dos outros.

Restrições

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

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 35% dos pontos, acontece sempre que X1_i, X2_i, Y_i ≤ 500 e N ≤ 100.

Para um conjunto de casos de teste valendo 70% dos pontos, acontece sempre que N ≤ 100, mas a coordenadas podem ter um qualquer valor entre 1 e 2 000 000 000.

Exemplo de Input

5
3 5 6
2 8 9
4 6 7
11 12 8
11 13 9

Exemplo de Output

4 3