The Ninja Way

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Input

Output

Sample Input

4 4
20
30
10
40
5 6
20
34
54
10
15
4 2
10
20
16
13
0 0

Sample Output

3
3
-1

Hint

 

Source

2009 Mid-Atlantic Regional Programming Contest