Problem E
Jupiter Orbiter

The Juno spacecraft in front of Jupiter. Graphic by NASA

Although we imagine interplanetary probes to be very sophisticated pieces of technology, their information systems are quite archaic. You might assume that they have a certain amount of contiguous main memory and can store their data wherever is convenient, but unfortunately that is not the case. The probe’s main memory is organised in a number of FIFO (first-in-first-out) queues. In such a queue, data has to be taken out of the queue in the same order as it has been added to it.

A probe has multiple sensors and each sensor is linked to one of the queues. Whenever a sensor finishes recording, it appends the generated data to its queue. A sensor can write data to the queue only if the queue has enough space left to take all the data; if not, the data is lost.

In order to transfer data from the probe to Earth (in a process called downlinking), the path between the satellite and Earth must not be blocked by anything (e.g. a planet like Jupiter) and the antenna must be correctly positioned. During each downlink opportunity, data can be taken from multiple queues and transmitted back to Earth. The total amount of data that can be transmitted during a downlink opportunity depends on the length of the downlink opportunity and distance to Earth. Sensors do not collect data during downlink opportunities, since all electricity available is devoted to the transmitter.

The most important thing for scientists is not to lose any data recorded by sensors. In particular, all queues have to be empty after the last downlink opportunity. The scientists have asked you to write a program to determine whether all data can be transferred to Earth in a given time frame.

Input

• one line containing three positive integers $n,q,s$ ($1\leq n,q \leq 30$, $1 \leq s \leq 100$), the number of downlink windows, FIFO queues, and sensors, respectively.

• one line with $s$ integers $q_1 \ldots q_ s$ ($1 \leq q_ i \leq q$ for each $i$), determining for each sensor the queue it feeds its data into.

• one line with $q$ integers $c_1 \ldots c_ q$ ($1 \leq c_ i \leq 10^6$ for each $i$), determining for each queue the size of the queue in megabytes.

• $n$ lines, each describing one downlink window. Each contains $s + 1$ non-negative integers.

  • The first integer $d$ ($1 \leq d \leq 10^6$) states the number of megabytes that can be transferred to earth during the window.

  • The following $s$ numbers $a_1 \ldots a_ s$ ($0 \leq a_ i \leq 10^6$ for each $i$) describing the amount of data (in megabytes) generated by each of the sensors after the last but before this downlink window.

There will never be new data during a downlink window.

Output

Output “possible” if it is possible to transfer all data to Earth, and “impossible” otherwise.

2 2 2
1 2
3 3
5 2 2
5 2 2

possible

2 2 2
1 2
3 3
1 2 2
5 2 2

impossible