`You are in an amusement park from time 0 to l. There are n types of trains you can play with. Each journey on the ith typeof train lasts d minutes. The ith train have several start times. You can join and exit in the middle of the journey of a train. You never join the same train twice.
Determine the minimum number of times you should join a train to spend all your time.
Note: If you finish a journey at t, then the next journey should be started exactly at t not t+1. You should start exactly at 0 and finish exactly on l.
Input format:
The first line contains n, l.
Each of next n lines contain train d, t where d is the duration of each journey of this train and t is the number of times it starts its journey.
Then t numbers are provided in increasing order. Each number determines a start time for a journey of this train.
Output Format:
Determine the minimum number of times you should join a train to spend all the time. If impossible to spend all time print -1.
Constraints:
1<=n<=20
1<=d<=l<=10^9
1<=c<=1000
Sample Input
4 101
51 3 15 29 55
41 2 0 65
31 2 21 90
19 1 0
Sample Output
3
Explanation:
We should attend the first journey of the fourth train from time 0 to time 19. Then we join the first journey of the first train from time 19 to time 66. Finally, we join the last journey of second train from time 66 to time 101.