Buying Notebooks

Minhyuk wants to buy $N$ notebooks. He has already surveyed the notebook prices at $M$ online stores.

Store $i$ sells one notebook for $p_i$ won and has $s_i$ notebooks in stock. Placing an order with a store incurs a shipping fee of $o_i$ won, charged only once no matter how many notebooks you buy. You may not order more than the $s_i$ notebooks a store has in stock.

Write a program that computes the minimum cost of buying $N$ notebooks.

The first line contains the number of test cases $T$ ($T \le 100$). Each test case has the following format.

• The first line contains the number of notebooks to buy $N$ and the number of stores $M$ ($1 \le N \le 10{,}000$, $1 \le M \le 100$, $N \le \sum s_i$).
• Each of the next $M$ lines contains a store's stock $s_i$, price $p_i$, and shipping fee $o_i$ ($0 \le s_i, p_i \le 10{,}000$, $0 \le o_i \le 1{,}000{,}000$).

For each test case, print the minimum cost of buying $N$ notebooks on its own line.