공책 구매

민혁이는 공책을 N개 사려고 한다. 민혁이는 온라인 쇼핑몰 M개에서 파는 공책의 가격을 모두 조사해놓았다.

i번째 쇼핑몰에서 파는 공책의 가격은 하나당 pi원이고, 총 si개가 준비되어 있다. 또, 배송비는 oi원이다. 민혁이는 si개를 넘게 주문할 수 없으며, 몇 개를 주문하더라도 배송비는 1번만 내면 된다.

공책 N개를 사는 비용의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T (T ≤ 100)가 주어지며, 아래와 같은 형식으로 이루어져 있다.

• 첫째 줄에 사려고 하는 공책의 개수 N과 쇼핑몰의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 100, N ≤ Σsi)
• M개의 줄에 si, pi, oi가 주어진다. (0 ≤ si, pi ≤ 10,000, 0 ≤ oi ≤ 1,000,000)

각각의 테스트 케이스마다 민혁이가 공책 N개를 구매하기 위한 비용의 최솟값을 출력한다.