All submissions for this problem are available.
Allen Rusk is building Latex. Latex is a modern typesetting software which will be known for its letter AI. Note that Latex is a modern software and supports way more than 26 letters. The letter AI consists of a database of letter pairs with a hit-rate and type associated with every pair. Since Latex is in beta stage, there are only two types of letter pairs right now: Modern and Rustic.
Today Allen is testing Latex.
Each test starts with a Test-Sum TS set to 0 and Type-Sum PS set to 0. The test consists of N phases where N is the total number of distinct letters available to him. For the first phase he chooses a random letter and writes it down. For each subsequent phase, he chooses a letter R which has not been written down and also that there exists a letter L which has been written down and the letter pair L R exists in the AI database. He also adds the hit-rate of L - R to his Test-Sum TS. Also, if the letter pair is Modern, he adds 1 to his Type-Sum.
At the end of each test he checks his Type-Sum. X is his lucky number. Hence if the Type-Sum is equal to X or N - 1 - X, he notes down the Test-Sum for this test.
Allen doesn't have much to do today, and he spends the whole day testing Latex. So much so that he exhausts all tests that are possible with the given Letter AI database. Finally, he finds out the minimum among all the Test-Sums he noted in the entire day. However, this has been tiring for him and he wonders whether he can find out the Minimum Test-Sum given just the AI database. Can you?
- First line containts a single integer T denoting the number of test cases. The description of T test cases follows.
- First line of each test case consists of 4 space separated integers N, M1, M2, X where N is the no. of distinct letters, M1 is the no.of pairs in AI database with type as Modern, M2 is the no. of pairs in AI database with type as Rustic and X is the lucky number.
- Next M1 lines for Modern type contains 3 space separated integers L, R, H denoting that pair L, R have type modern and hit rate H
- Next M2 lines for Rustic type contains 3 space separated integers L, R, H denoting that pair L, R have type rustic and hit rate H
- For each test case, output a single line containing the minimum test sum TS that he obtained with type sum equal to X or N - 1 - X. If there doesn't exist any such test print -1
- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 200
- 1 ≤ M1 + M2 ≤ 600
- 0 ≤ X ≤ N - 1
- 1 ≤ L, R ≤ N
- 1 ≤ H ≤ 100
Sample Input: 1 5 3 2 1 1 2 1 2 3 1 3 4 1 4 5 1 3 5 1 Sample Output: 4
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions