Programmed Attack
By Cristhian Bonilha, UTFPR 
Brazil
By Cristhian Bonilha, UTFPR Brazil
You are the leader of an elite soldier’s team, and have just been informed that the soldiers that you recently sent to attack some enemy posts were captured and kept as hostages. Your strategy now is to redeem your soldiers without losing any soldiers in battle, and without ever letting the enemies sound the alarm.
There are N enemy posts and M line visions between them, in a way that if there is a line vision from post A to post B, the soldiers from post A would know if post B was being attacked and would sound the alarm. As your goal is total description, you decided to only attack a post if, and only if, all the posts that have a line vision to this one had been attacked already, this way avoiding the alarm to be sound.
Initially you have S soldiers on your team. On each enemy post there are E enemy soldiers and F of your soldiers as hostages. To guarantee that each attack is a success, you decided to only attack a post when the number of soldiers on your troop is bigger than the number of soldiers on that post. After each attack, the hostage soldiers join your team to help on the next attacks.
The plan sounds good, but we need absolute certainty that it is possible to execute it. With the data about the posts collected by your spy, find out if it is possible to attack all the enemies’ posts respecting the two restrictions given above.
There will be at most 30 test cases. Each test case starts with three integers, N, M and S, representing the number of posts, the number of line visions, and the number of soldiers that are initially on your team, respectively (1 ≤ N ≤ 104, 0 ≤ M ≤ 105, 1 ≤ S ≤ 100).
Following there will be a line with N integers ei, where the i-th integer represents how many enemy soldiers there are on the i-th post (1 ≤ ei ≤ 106, for each 1 ≤ i ≤ N).
Following there will be a line with N integers fi, where the i-th integer represents how many hostage soldiers there are on the i-th post (0 ≤ fi ≤ 100, for each 1 ≤ i ≤ N).
Following there will be M lines, each containing two integers A and B each, representing that the post A has a line vision on the post B (1 ≤ A, B ≤ N, A <> B).
The last test case is indicated when N = M = S = 0, which should not be processed.
For each test case print one line, containing the word “possivel” if it is possible to attack all the posts respecting the two restrictions given, or “impossivel” otherwise.
| Input Sample | Output Sample |
|
2 1 2 |
possivel |