In conjunction with the IOI, Pattaya City will host a race: the International Olympiad in Racing (IOR) 2011. As the host, we have to find the best possible course for the race.
In the Pattaya-Chonburi metropolitan area, there are cities connected by a network of highways. Each highway is bidirectional, connects two different cities, and has an integer length in kilometers. Furthermore, there is exactly one possible path connecting any pair of cities. That is, there is exactly one way to travel from one city to another city by a sequence of highways without visiting any city twice.
The IOR has specific regulations that require the course to be a path whose total length is exactly kilometers, starting and ending in different cities. Obviously, no highway (and therefore also no city) may be used twice on the course to prevent collisions. To minimize traffic disruption, the course must contain as few highways as possible.
Write a program that takes the following parameters:
- – the number of cities. The cities are numbered through .
- – the required distance for the race course.
- – a two-dimensional array representing highways. For , highway connects the cities and .
- – a one-dimensional array representing the lengths of the highways. For , the length of highway is .
You may assume that all values in the array are between and , inclusive, and that the highways described by this array connect all cities as described above. You may also assume that all values in the array are integers between and , inclusive.
Your program must output the minimum number of highways on a valid race course of length exactly . If there is no such course, your program must output
Consider the case shown in Figure 1, where , ,
The course can start in city , go to city , and terminate in city . Its length will be exactly km + km = km, and it consists of two highways. This is the best possible course; therefore your program must output .
Consider the case shown in Figure 2, where , ,
There is no valid course. In this case, your program must output
Consider the case shown in Figure 3, where , ,
One possible course consists of 3 highways: from city via city and city to city . Another course starts in city and goes via city to city . Both of these courses have length exactly km, as required. The second one is optimal, as there is no valid course with a single highway. Hence, your program must output .
- Line : and
- Lines to : information on the highways; i.e., line contains , , and , separated by a space, for .
One integer, the expected solution.
Sample Input 1
4 3 0 1 1 1 2 2 1 3 4
Sample Output 1
Sample Input 2
3 3 0 1 1 1 2 1
Sample Output 2
Sample Input 3
11 12 0 1 3 0 2 4 2 3 5 3 4 4 4 5 6 0 6 3 6 7 2 6 8 5 8 9 6 8 10 7
Sample Output 3
Subtask 1 (9 points)
- The network of highways forms the simplest possible line: For , highway connects cities and .