18588번 - Milk Candy 다국어

Calabash is now playing an RPG game on his computer. In this game, there are n unknown numbers x₁, x₂, . . . , x_n and m NPCs selling hints. The i-th NPC is selling c_i hints. Each hint contains three integers, l_j, r_j, and w_j, which means Calabash can pay w_j coins to buy this hint, and this hint can tell Calabash the value of x_lj + x_lj+1 + . . . + x_rj−1 + x_rj.

The goal of the game is to figure out all the n unknown numbers. Clever Calabash knows how to buy hints optimally, but NPCs are greedy: for the i-th NPC, Calabash must buy exactly k_i hints from him. Note that a single hint can’t be bought more than once.

This problem is much more difficult for Calabash. Please write a program to help Calabash find the minimum number of coins he needs to pay to figure out all numbers, or determine that it is impossible.

The first line of the input contains an integer T (1 ≤ T ≤ 10), denoting the number of test cases.

In each test case, there are two integers n and m (1 ≤ n, m ≤ 80) on the first line, denoting the number of unknown numbers and NPCs.

Then follow m parts. Each part starts with a line with two integers c_i and k_i (1 ≤ k_i ≤ c_i), denoting the number of hints the i-th NPC has and the limit for the i-th NPC.

Each of the next c_i lines contains three integers, l_j, r_j, and w_j (1 ≤ l_j ≤ r_j ≤ n, 1 ≤ w_j ≤ 10⁶), describing the hints offered by the i-th NPC.

It is guaranteed that, in each test case, the sum of all c_i is at most 80.

For each test case, print a single line containing an integer denoting the minimum number of coins. If there is no solution, output “-1” instead.