Decisão de Ajuste de Rota para Carona em Avante 3

Algoritmo 5 Avante 3 Expert Tempo máximo de execução 1s DESCRIÇÃO Descrição O computador de bordo calculou um caminho que levrará Oto até Avante 3 porém Oto recebeu uma mensagem solicitando que as naves a caminho de Avante 3 dessem carona para um indivíduo no caminho e eles pagariam por isso Como a rota de Oto já está calculada ele precisa decidir se ajustará a rota para dar carona ao indivíduo ou não Acontece que a mudança de rota tem um custo e ele só fará a mudança se o valor que Avante 3 pagará for maior ou igual que o custo que ele terá caso contrário ele deixará a carona a cargo de outra nave As rotas são descritas por cadeias de caracteres representando a sequência de vias pelas quais Oto deve seguir até chegar ao seu destino em Avante 3 Cada via é representada por um único caractere maiúsculo e as hipervias são diferenciadas das vias planetárias através do caractere que precede o caractere que representa a hipervia Perceba que um mesmo caractere pode representar uma via planetária ou uma hipervia e essas vias são diferenciadas pela presença do caractere antecedendo o caractere em questão Existem cinco tipos de mudanças de rota troca de via planetária por hipervia troca de hipervia por via planetária troca de via do mesmo tipo via planetária por via planetária ou hipervia por hipervia atalho remoção de via ou hipervia desvio inserção de via planetária ou hipervia A troca de uma via planetária por uma hipervia possui custo 2 a troca de uma hipervia por uma via planetária possui custo 2 troca de via do mesmo tipo possui custo 1 um atalho possui custo 1 e um desvio possui custo 3 Formato de entrada A primeira linha da entrada é dada por três números inteiros N M 1 N M 10000 e K 0 K 1000 que representam respectivamente o número de vias na rota original de Oto o número de vias na nova rota que Oto teria que fazer para dar a carona e o valor pago por Avante 3 pela carona A seguir são apresentadas duas linhas onde a primeira contém a lista de vias na rota original de Oto e a segunda a lista na nova rota Formato de saída Caso o custo da mudança de rota seja menor ou igual que o valor pago por Avante 3 a saída será dada por uma linha contendo a seguinte frase sem as aspas Lucro X A caminho onde X deve ser substituido pelo número inteiro que indica quanto Oto ganhará pela carona Caso o custo da mudança de rota seja maior que o valor pago por Avante 3 a saída será a seguinte frase sem aspas e sem os acentos Carona inviavel favor solicitar a outra nave Exemplos de Entrada 5 5 5 TJKKN WKJYN Saída Lucro 1 A caminho