Buying Notebooks

Interview

Time limit1sMemory limit128 MB

Summary

Each store has a fixed shipping fee, a per-notebook price, and limited stock; buy exactly N notebooks across stores at minimum total cost.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Greedy, Array
Solved: No attempts yet

Problem

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.

Input

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$ ).

Output

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

Examples2

Example 1

Input

Expected output

118
100

Example 2
Input
```
1
1 1
1 5 3
```
Expected output
```
8
```