공책 구매

민혁이는 공책을 $N$권 사려고 한다. 온라인 쇼핑몰 $M$곳에서 파는 공책 가격을 모두 조사해 두었다.

$i$번째 쇼핑몰은 공책 한 권을 $p_i$원에 팔며, 재고는 $s_i$권이다. 이 쇼핑몰에 주문하면 몇 권을 사든 배송비 $o_i$원이 한 번만 붙는다. 한 쇼핑몰에서는 재고 $s_i$권을 넘겨 주문할 수 없다.

공책 $N$권을 사는 데 드는 최소 비용을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$ ($T \le 100$)가 주어진다. 각 테스트 케이스는 다음 형식을 따른다.

• 첫째 줄에 사려는 공책의 수 $N$과 쇼핑몰의 수 $M$이 주어진다. ($1 \le N \le 10{,}000$, $1 \le M \le 100$, $N \le \sum s_i$)
• 이어지는 $M$개의 줄에 각 쇼핑몰의 재고 $s_i$, 가격 $p_i$, 배송비 $o_i$가 주어진다. ($0 \le s_i, p_i \le 10{,}000$, $0 \le o_i \le 1{,}000{,}000$)

각 테스트 케이스마다 공책 $N$권을 사기 위한 최소 비용을 한 줄에 출력한다.