시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 2 2 50.000%

문제

민혁이는 공책을 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개를 구매하기 위한 비용의 최소값을 출력한다.

예제 입력

2
20 4
5 5 6
10 4 12
15 6 9
20 7 0
10 2
5 0 50
1000 10 0

예제 출력

118
100

힌트