Minimal Playlist Duration

Alice is building a playlist using a collection of songs. There are N songs, each with a unique title and a duration in minutes. She wishes the playlist to have a total duration of at least M minutes. In addition, she is allowed up to K merge operations. Each merge operation is given as a tuple of two song titles and a new duration – if both songs exist then the two songs may be merged into one song having the new duration, effectively removing one song from the list.

Your task is to determine the smallest total duration that can be formed by selecting a nonempty subset of songs (after optionally applying any one merge operation at a time, each considered independently) such that the total duration is not less than M minutes. If no such subset exists, print -1.

The operations are not chained; each merge operation is considered on the original list to see if it makes a better solution.

Note: All formulas are in \(\LaTeX\) format. For example, the required duration condition is \(\sum_{i \in S} d_i \ge M\), where \(S\) is a subset of selected songs and \(d_i\) is the duration of song \(i\).

inputFormat

The input is given via standard input (stdin) and has the following format:

T
N M
Title1 Duration1
Title2 Duration2
... 
TitleN DurationN
K
TitleA1 TitleB1 NewDuration1
TitleA2 TitleB2 NewDuration2
...
TitleAK TitleBK NewDurationK

The first line contains an integer T denoting the number of test cases. For each test case:

• The first line contains two integers N and M.
• The next N lines each contain a string (song title) and an integer (duration), separated by a space.
• The next line contains an integer K (the number of merge operations available).
• The next K lines each contain two song titles and an integer (the new duration if the two songs are merged), each separated by a space.

outputFormat

For each test case, output a single integer: the smallest total duration of any subset of songs (possibly updated with one merge operation) that is at least M minutes, or -1 if it is impossible. The result should be printed to standard output (stdout).

## sample

1
3 10
hiphop 3
rap 2
blues 1
1
hiphop rap 4

-1

</p>