O tesouro milenar de Bagas da Colina está depositado ao longo de N quilómetros. Escavá-lo ao longo do quilómetro i do depósito levaria a um lucro de Li (ou prejuízo, se Li < 0). No entanto, estes valores não são conhecidos.
O capitão Joaquim Pardal, ex-pirata e atual caçador de tesouros, está muito interessado neste tesouro. Como tal, realizou M prospeções do solo na região, obtendo de cada uma delas informação do tipo "Ao escavar o segmento entre os quilómetros A e B, o lucro total obtido é menor/maior ou igual que X", ou seja, sabemos que o lucro ou é maior ou igual que um certo valor X ou que é menor ou igual que X.
O capitão não tem os meios para escavar o tesouro sozinho e, como tal, quer pedir um empréstimo à Organização Nacional de Investimentos. Para os convencer, ele vai mostrar-lhes as M prospeções e a estimativa de lucro mais otimista: o lucro máximo de escavar todo o depósito que é coerente com as prospeções realizadas. Consegues ajudar o capitão Joaquim Pardal a encontrar este valor? Nota que é possível que o valor seja infinito ou que não exista nenhum depósito que respeite as M prospeções
Vejamos um exemplo. Seja N = 4 e M = 3 com as seguintes regras:
Um conjunto de lucros que satisfaz esta restrição é L = 3 2 0 1, e a soma de todos os elementos é 6, logo a resposta seria 6.
Um outro exemplo, seja N = 5 e M = 2 com as seguintes regras:
Um conjunto de lucros que satisfaz esta restrição é L = 1 1 0 1 1, e a soma de todos os elementos é 4, logo a resposta seria 4.
Se não tivessemos a última regra neste último exemplo então a resposta seria indeterminada (ou seja, podemos ter um lucro infinitamente grande), visto que podiamos ter INF 2 -INF 2 INF como resposta, onde INF representa um número arbitrariamente grande.
Dados inteiros N e M, considera uma lista desconhecida de N inteiros. São dadas M regras do tipo (S, A, B, X) que transmitem a informação que a soma dos valores da lista entre o A-ésimo e o B-ésimo da lista é menor ou igual (se S for 1) ou maior ou igual (se S for 2) do que X. Descobre o maior valor possível (coerente com as regras) para a soma dos N elementos da lista.
É possível que o valor seja infinito ou que não haja nenhuma lista que respeite as M regras. Se algum destes casos acontecer, deves respetivamente imprimir Indeterminado ou Impossivel.
Nota: Este problema é multiteste, o que significa que o vosso programa deve ler e resolver vários casos de teste de uma vez.
A primeira linha contém um inteiro T, o número de casos de teste. Seguem se T blocos de input cada um com o seguinte formato:
A primeira linha contém dois inteiros separados por espaços, N, que representa o comprimento da região e M, o número de regras. Seguem-se M linhas cada uma tem o seguintes formato:
O output deve conter T linhas, uma por cada caso de teste.
Nos casos em que existe solução, a linha deve conter um inteiro. Nos casos em que é impossível então devem conter a palavra Impossivel e nos casos em que o máximo é infinito deve conter a palavra Indeterminado.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ T ≤ 10 | Número de casos de teste | |
| 1 ≤ N ≤ 2000 | Comprimento | |
| 1 ≤ M ≤ 2000 | Número de regras |
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 ≤ 20, M ≤ 100, a solução tem todos os elementos a 0 / 1 e existe sempre |
| 2 | 25 | N ≤ 200, M ≤ 400 e sempre que existir uma restrição (1, A, B, X) também existe (2, A, B, -X) e vice-versa. |
| 3 | 25 | N ≤ 200, M ≤ 400 |
| 4 | 30 | - |
3 4 3 1 1 2 5 1 2 4 3 2 2 2 2 5 3 1 1 3 2 1 3 5 2 2 3 3 0 5 2 1 1 3 2 1 3 5 2
6 4 Indeterminado