All submissions for this problem are available.
Credenz'14 design team is doing their best to paint the main poster. However they are stuck in a problem. There are N colors in total numbered as 1, 2, 3 . . N . The main poster needs Ai color quantity of the ith color.
The design team has a set of N colors, ith color being of quantity Bi.
There are some colors which can be obtained from a combination of some other colors. Also those colors can be broken into the same combination of colors. The Design team wants to know if the colors needed for the main poster can be fulfilled by the set of colors it has.
If the design team has colors more than or equal to that needed for the main poster, the poster can be made.
Also, one color can be formed by a maximum of one combination of some colors.
The first line contains an integer N, the total number of colors.
N lines follow, ith line containing an integer x, the number of colors from which the ith color can be obtained or can be broken into, followed by the list of x numbers from which the ith color can be obtained or can be broken into.
Next line contains N spaced integers, A1 A2 ... AN
Next line contains N spaced integers, B1 B2 ... BN
print "POSSIBLE" if the poster can be painted otherwise print "IMPOSSIBLE"
1 ≤ N ≤ 10^5
0 ≤ Ai ≤ 10^9
0 ≤ Bi ≤ 10^9
0 ≤ x < N
Sum of all x ≤ 2*N
Input: 5 0 1 1 0 0 0 2 0 1 1 1 1 1 1 1 1 Output: POSSIBLE
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions
If you are still having problems, see a sample solution here.