Island tours

Hugo is organizing wildlife tours on the islands of a remote Pacific archipelago. His klients are mostly members of various botanical societies and universities and they are eager to visit as many different floral habitats as possible during one tour.
From the botanical point of view each island belongs to one of a few specific types which are characterized by their rare endemic plants. It turned out that it is always enough to visit at most one island of a particular type during one tour. Visiting two or more islands of the same type during one tour may leave the participants bored and less satisfied, Hugo wants to avoid such outcome. He also strives to make his tours offer highly attractive so he is considering only such tours each of which will visit islands of all types. On the other hand, his planning is limited by the transport options which are available between the islands. Due to the distance between the islands and many unpredictable dangerous ocean currents it so happens that there are no direct ferry connections between some pairs of islands. Those connections which do exist are priced differently. The price for travelling in one direction may differ from the price for traveling in the opposite direction. Sometimes, there may be only one way connection available between two islands.
To add to the complexity of the task, the price for any tour should not exceed some given fixed limit. High prices may discourage the visitors from taking the tours.
Hugo has the list of all connections and their prices and he knows the price limit. He is interested in finding out what is the cheapest tour he can organize. There is no extra price for staying at any island during the tour, all costs are included in corresponding ferry prices. The tour starts and begins on the same island. This island is the only one which type may be visited twice during the tour.

     


Image 1. Example of the ferry connections between the six islands comprising the archipelago. The types of islands are denoted by capital letters A, B, C. The ferry prices are written at the particular connections. The connections of the cheapest tour are highlighted in red.

The task

You are given a list of islands and their types and a complete list of ferry connections between the islands together with their prices. Find the price of the cheapest tour which visits islands of all types and does not visit any island type twice except for the island on which the tour starts and ends. The price should not exceed a given prescribed limit which you are given too.

Input

First line of input contains two integers N, L, separated by space. The value N represents the number of islands. The islands are labeled 0, 1, 2, ..., N−1. L is the price limit for the tour.
Next, there are N lines, each line describes one island, its type, and the ferry connections which start at this island. Each line begins with an integer representing the label of the island. The label is followed by a single capital letter denoting the type of the island. These values are folowed by the list of ferry connections which start at this island. The list begins with the integer representing the size of the list. Each list item consists of two values. The first value is the label of the destination island and the second value is the price of the connection. All input values on one line are separated by one or more spaces.
There are at most 10 different types of the islands, denoted by the letters A, B, C, ..., J. The number of islands in the archipelago does not exceed 200. There is always at most one ferry connection between any two islands in each direction. All ferry costs are positive and less than 1000.

Output

Output contains one text line with one integer representing minimum price of the tour satisfying the conditions given above. You may assume that there always exist at least one such tour.

Example 1

Input
6 15
 0  B   2     5  3    2  7
 1  A   2     0  5    3  2
 2  A   2     1  1    4  5
 3  B   2     2  3    5  6
 4  C   2     3  2    0  5
 5  C   2     4  1    1  6
Output
10
The example is depicted in the Image 1.

Example 2

Input
15 30
 0  A   1     1  3
 1  B   1     6  8
 2  A   2     1  1    3  7
 3  B   1    10  7
 4  E   2     0  4   11  4
 5  D   1     4  7
 6  C   2     5  5    7  4
 7  B   1     8  2
 8  D   2     2  7   13  5
 9  C   1     8  8
10  E   1     9  3
11  B   1    12  5
12  A   1     6  4
13  B   2    12  3   14  6
14  A   1    10  5
Output
25
The cheapest tour visits islands with labels 4, 11, 12, 6, 5.

Example 3

Input
12 60
 0  C   9     1 16    2 11    3 20    4 14    7 19    8 11    9 17   10 17   11 14
 1  E   5     2 20    3 18    4 15    5 19    9 18
 2  F   8     0  9    1  7    3 11    5 10    7 15    9 10   10 19   11 20
 3  D   5     0 10    2  6    5 10    8  6   11  6
 4  A   5     3 16    5  9    6 18    9  9   10 19
 5  A   7     2  6    3  9    4 11    6  9    7 16    9 12   10 17
 6  D   6     0 15    3 12    8 17    9 12   10 11   11 14
 7  E   8     0 17    1 17    2 12    4 15    5 10    6  6    8 15    9 17
 8  D   4     0 14    5 11    7  7    9  9
 9  A   7     1  5    2 12    4  7    5 18    6 13    7 18   11 12
10  C   6     0 15    1 10    3 20    4 14    6  5   11 14
11  B   8     0 10    1  6    2 12    4  7    6 11    7 15    8  6   10  6
Output
52
The cheapest tour visits islands with labels 0, 11, 8, 7, 5, 2.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set