Problema do Pedágio Espacial: Minimização de Custos de Tickets

Algoritmo 5 Pedágio Espacial Expert Tempo máximo de execução 1s DESCRIÇÃO Descrição Oto encontrou uma rota segura até Poseidônia agora precisa comprar tickets de pedágio para completar sua viagem Os tickets de pedágio são vendidos por conjuntos de dias Sabendo os dias em que Oto irá precisar viajar é preciso escolher o melhor conjunto de tickets para fazer todo o percurso com o menor custo possível Formato de entrada A primeira linha da entrada é dada por dois números inteiros N e M 1 N M 10000 indicando respectivamente o número de tickets disponível para a compra e o número de dias que Oto precisará viajar Os dias são representados por números que indicam a quantidade de dias após o dia atual ou seja são datas relativas ao dia de hoje Não se assuste com a quantidade de dias os dias seguem o calendário intergalático unificado que possui uma duração muito menor que o tempo de uma rotação completa do planta Terra A seguir são apresentadas N linhas contendo três números i j 1 i j M e k 1 k 1000 separados por um espaço indicando o primeiro dia i e o último dia j para o qual aquele ticket é válido além do seu preço k Formato de saída A saída é dada por um único número inteiro indicando qual o menor valor que Oto pode pagar para completar sua viagem Caso não seja possível realizar a viagem com os tickets disponíveis devese imprimir a seguinte mensagem sem as aspas Vias lotadas Exemplos de Entrada 5 15 1 3 10 2 3 12 5 9 20 5 13 25 10 15 5 Saída Vias lotadas Entrada 5 15 1 3 10 2 5 12 5 10 20 4 13 25 10 15 5 Saída 40