Jupiter Orbiter

A planetary probe sounds like advanced hardware, but its information system is plain. There is no wide block of main memory to lay data out in. The main memory of the probe is split into several FIFO queues, and data can leave a queue only in the order it entered.

The probe carries several sensors, and each sensor is wired to one queue. When a sensor finishes a recording, it appends the data it produced to the end of its queue. A sensor writes only when the queue has room left for all of that data. If the room is not there, the data is gone.

Sending data from the probe down to Earth is called downlinking. It requires that no body such as Jupiter blocks the path between the probe and Earth, and that the antenna points the right way. During one downlink opportunity the probe can pull data out of several queues and transmit it together. The total amount one opportunity carries is set by the length of the opportunity and the distance to Earth. Sensors collect nothing during a downlink, because all available power goes to the transmitter.

What matters most to the scientists is losing none of the data the sensors recorded. Every queue has to be empty once the last downlink opportunity ends. Write a program that decides whether all data can reach Earth within the given schedule.

The first line contains the number of downlink opportunities $n$, the number of queues $q$, and the number of sensors $s$ ($1 \le n, q \le 30$, $1 \le s \le 100$).

The second line contains $s$ integers $q_1, \dots, q_s$. Here $q_i$ is the number of the queue that sensor $i$ writes into ($1 \le q_i \le q$).

The third line contains $q$ integers $c_1, \dots, c_q$. Here $c_i$ is the size of queue $i$ in megabytes ($1 \le c_i \le 10^6$).

Each of the next $n$ lines describes one downlink opportunity in chronological order. Each line holds $s + 1$ non-negative integers.

• The first integer $d$ is the amount of data that can be sent to Earth during that opportunity ($1 \le d \le 10^6$).
• The following $s$ integers $a_1, \dots, a_s$ are the amounts of data each sensor produced after the previous downlink opportunity ended and before this one starts ($0 \le a_i \le 10^6$).

No new data appears while a downlink opportunity is running. All queues are empty at the start.

Print possible if all data can be sent to Earth, and impossible otherwise.