Calabash is now playing an RPG game on his computer. In this game, there are nnunknown numbers x1,x2,…,xnx1,x2,…,xn and mm NPCs selling hints. The ii-th NPC is selling cicihints. Each hint contains three integers lj,rj,wjlj,rj,wj, which means Calabash can pay wjwjcoins to buy this hint, and this hint can tell Calabash the value of xlj+xlj+1+⋯+xrj−1+xrjxlj+xlj+1+⋯+xrj−1+xrj.
The target of the game is to figure out all the nn unknown numbers. Clever Calabash knows how to buy hints optimally, but NPCs are greedy, for the ii-th NPC, Calabash must buy exactly kiki hints from him. Note that each 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 cheapest way, or determine it is impossible.
Input
The first line of the input contains an integer T(1≤T≤10)T(1≤T≤10), denoting the number of test cases.
In each test case, there are two integers n,m(1≤n,m≤80)n,m(1≤n,m≤80) in the first line, denoting the number of unknown numbers and NPCs.
For the next mm parts, there are two integers ci,ki(1≤ki≤ci)ci,ki(1≤ki≤ci) in the first line, denoting the number of hints the ii-th NPC has and the limit for the ii-th NPC.
For the next cici lines, each line contains three integers lj,rj,wj(1≤lj≤rj≤n,1≤wj≤106)lj,rj,wj(1≤lj≤rj≤n,1≤wj≤106), describing each hint offered by the ii-th NPC.
It is guaranteed that ∑ci≤80∑ci≤80 in each test case.
Output
For each test case, print a single line containing an integer, denoting the minimum number of coins. If there is no solution, output ``-1-1'' instead.