uCoder | 1169 | Nível: 4 | Tempo Limite: 10
Ataque Programado
Adaptado por erich.rodriguesf
Você é o lider de uma equipe de soldados de elite, e acaba de descobrir que os soldados que você enviou recentemente para atacar os postos inimigos foram capturados e mantidos como refém. Sua estratégia agora é recuperar sua tropa sem perder um soldado em batalha, e sem nunca deixar que o inimigo soe o alarme.
Existem N postos inimigos e M linhas de visão entre eles, de tal modo que se existe uma linha de visão do posto A ao posto B, os soldados do posto A saberiam quando o posto B fosse atacado e soariam o alarme. Como seu objetivo é total descrição você decidiu que só atacaria um posto quando todos os postos que tem linha de visão sobre ele tivessem sido atacados anteriormente, o que impossibilitaria que o alarme fosse soado.
Inicialmente você tem S soldados em sua tropa. Em cada posto inimigo há E soldados inimigos e F soldados reféns. Para garantir que cada ataque seja um sucesso, você decidiu que só vai atacar um posto quando o número de soldados em sua tropa for maior que o número de soldados inimigos daquele posto. Após cada ataque, os soldados reféns daquele posto são adicionados à sua tropa para os próximos ataques.
O plano parece bom, mas é preciso ter absoluta certeza de que é possível completá-lo. Com os dados sobre os postos trazidos pelo seu espião, descubra se é possível atacar todos os postos inimigos seguindo as duas restrições acima.
Entrada
Haverá no máximo 30 casos de teste. Cada caso de teste inicia com três inteiros, N, M e S, indicando o número de postos, o número de linhas de visão e o número inicial de soldados de elite em sua equipe, respectivamente (1 ≤ N ≤ 10⁴, 0 ≤ M ≤ 10⁵, 1 ≤ S ≤ 100).
Em seguida haverá uma linha com N inteiros ei, onde o i-ésimo inteiro indica quantos soldados inimigos há no posto i (1 ≤ ei ≤ 10⁶, para todo 1 ≤ i ≤ N).
Em seguida haverá uma linha com N inteiros fi, onde o i-ésimo inteiro indica quantos soldados reféns há no posto i (0 ≤ fi ≤ 100, para todo 1 ≤ i ≤ N).
Em seguida haverá M linhas, cada uma contendo dois inteiros A e B, indicando que o posto A tem uma linha de visão sobre o posto B (1 ≤ A, B ≤ N, A <> B).
O último caso de teste é indicado quando N = M = S = 0, o qual não deverá ser processado.
Saída
Para cada caso de teste imprima uma linha, contendo a palavra “possivel” caso seja possível atacar todos os postos respeitando as restrições dadas, ou “impossivel” caso contrário.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
2 1 2 |
possivel |