Zak Galou

Zak Galou é um famoso bruxo matador de monstros. Diz a lenda que existe uma caverna escondida nos confins da selva contendo um tesouro milenar. Até hoje nenhum aventureiro conseguiu recuperar o tesouro, pois ele é bem guardado por terríveis monstros. Mas Zak Galou não é um aventureiro qualquer e decidiu preparar-se para recuperar o tão sonhado tesouro.

Zak Galou dispõe de uma certa quantidade de mana (uma espécie de energia mágica) e de uma lista de $M$ magias. Cada monstro tem um determinado número de pontos de vida. Cada vez que Zak Galou lança uma magia contra um monstro, Zak gasta uma certa quantidade de mana (o custo da magia) e inflinge um certo dano ao monstro. O dano inflingido provoca a perda de pontos de vida do monstro (o número de pontos perdidos depende da magia). Um monstro está morto se tiver zero ou menos pontos de vida. Zak sempre luta contra um monstro a cada vez. Como é um bruxo poderoso, ele pode usar a mesma magia várias vezes, desde que possua a quantidade necessária de mana.

Em suas pesquisas, Zak Galou conseguiu o mapa do tesouro. A caverna é representada como um conjunto de salões conectados por galerias. Os salões são identificados sequencialmente de $1$ a $N$. Zak sempre inicia no salão $1$ e o tesouro está sempre no salão $N$. Existem $K$ monstros identificados sequencialmente de $1$ a $K$. Cada monstro vive em um salão, do qual não sai (note que é possível que mais de um monstro viva no mesmo salão). Durante a busca pelo tesouro, Zak Galou pode sair ou recuperar o tesouro de um salão somente se o salão estiver vazio (sem monstro). Em outras palavras, Zak deve sempre, antes de sair ou de recuperar o tesouro de um salão, matar o(s) monstro(s) que lá viver(em).

Dadas as descrições das magias, dos monstros e da caverna, sua tarefa é determinar a quantidade mínima inicial de mana necessária para que Zak Galou consiga recuperar o tesouro.

Entrada