Little Tita has always been annoyed by coins, she’s so annoyed that has devised a formula to assign an annoyment level to each transaction. The formula is quite simple, each coin c has a transfer annoyment value (Tc) and a keep annoyment level (Kc), then, each transaction has a total annoyment level (A) defined as the sum of the transfer annoyment (AT) and the kept annoyment (AK). Where:

Given the list of coins that exist, the cost of a transaction and the list coins Tita has; find the minimum total annoyment level that Tita can guarantee for the transaction assuming the seller has an infinite amount of coins of each type and is not at all thinking about Tita’s annoyment level formula.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

Each test case will start with two integer N, the number of coin types that exist, and C, the cost of the transaction. The next N lines describe each coin type by with three integers Vi, Ti and Ki which represent the value, transfer annoyment and keep annoyment, respectively. Finally, a line with N integers Ai represent the amount of coins Tita has of each type, in the same order as the coins description.

Output

For each input case you must print a single line with the string Scenario #i: x, where i is the number of the test case (starting at 1), and x is the minimum annoyment level that Tita can guarantee for the transaction or −1 if the transaction cannot be made.

Input:
3
3 11
2 1 10
10 20 20
3 1 1
2 1 0
4 11
2 1 10
10 20 20
3 1 1
1 10 1
2 1 0 0
2 3
4 1 1
3 1 1
1 0

Output:
Scenario #1: 24
Scenario #2: 42
Scenario #3: -1