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

문제

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

예제 입력 1

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

예제 출력 1

118
100
W3sicHJvYmxlbV9pZCI6IjUzNzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjVcdWNjNDUgXHVhZDZjXHViOWU0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVhY2Y1XHVjYzQ1XHVjNzQ0IE5cdWFjMWMgXHVjMGFjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YzYyOFx1Yjc3Y1x1Yzc3OCBcdWMxZmNcdWQ1NTFcdWJhYjAgTVx1YWMxY1x1YzVkMFx1YzExYyBcdWQzMGNcdWIyOTQgXHVhY2Y1XHVjYzQ1XHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjODcwXHVjMGFjXHVkNTc0XHViMTkzXHVjNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5pXHViYzg4XHVjOWY4IFx1YzFmY1x1ZDU1MVx1YmFiMFx1YzVkMFx1YzExYyBcdWQzMGNcdWIyOTQgXHVhY2Y1XHVjYzQ1XHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0MCBcdWQ1NThcdWIwOThcdWIyZjkgcDxzdWI+aTxcL3N1Yj5cdWM2ZDBcdWM3NzRcdWFjZTAsIFx1Y2QxZCBzPHN1Yj5pPFwvc3ViPlx1YWMxY1x1YWMwMCBcdWM5MDBcdWJlNDRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YmMzMFx1YzFhMVx1YmU0NFx1YjI5NCBvPHN1Yj5pPFwvc3ViPlx1YzZkMFx1Yzc3NFx1YjJlNC4gXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IHM8c3ViPmk8XC9zdWI+XHVhYzFjXHViOTdjIFx1YjExOFx1YWM4YyBcdWM4ZmNcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YzczY1x1YmE3MCwgXHViYTg3IFx1YWMxY1x1Yjk3YyBcdWM4ZmNcdWJiMzhcdWQ1NThcdWIzNTRcdWI3N2NcdWIzYzQgXHViYzMwXHVjMWExXHViZTQ0XHViMjk0IDFcdWJjODhcdWI5Y2MgXHViMGI0XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2Y1XHVjYzQ1IE5cdWFjMWNcdWI5N2MgXHVjMGFjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKFQgJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHVhY2Y1XHVjYzQ1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1YzFmY1x1ZDU1MVx1YmFiMFx1Yzc1OCBcdWFjMWNcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwLDAwMCwgMSAmbGU7IE0gJmxlOyAxMDAsIE4gJmxlOyAmU2lnbWE7czxzdWI+aTxcL3N1Yj4pPFwvbGk+XHJcblx0PGxpPk1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIHM8c3ViPmk8XC9zdWI+LCBwPHN1Yj5pPFwvc3ViPiwgbzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IHM8c3ViPmk8XC9zdWI+LCBwPHN1Yj5pPFwvc3ViPiAmbGU7IDEwLDAwMCwgMCAmbGU7IG88c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwKTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViYmZjXHVkNjAxXHVjNzc0XHVhYzAwIFx1YWNmNVx1Y2M0NSBOXHVhYzFjXHViOTdjIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHViZTQ0XHVjNmE5XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTM3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV4dHJlbWUgU2hvcHBpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkpvaG4gd2FudHMgdG8gYnV5IGEgbGFyZ2UgbnVtYmVyIG9mIHdpZGdldHMuIEhlIGhhcyBhbHJlYWR5IGNvbXBpbGVkIGEgbGlzdCBvZiBzaG9wcyB0aGF0IHNlbGwgdGhlIHdpZGdldHMgaGUgbGlrZXMuPFwvcD5cclxuXHJcbjxwPkVhY2ggc2hvcCBtYXkgY2hhcmdlIGEgZGlmZmVyZW50IHByaWNlIHBlciB3aWRnZXQuIEFkZGl0aW9uYWxseSwgZWFjaCBzaG9wIG9ubHkgaGFzIGEgbGltaXRlZCBudW1iZXIgb2Ygd2lkZ2V0cyBpbiBzdG9jayAoYW5kIEpvaG4gZG9lcyBub3Qgd2FudCB0byBvcmRlciBvdXQtb2Ytc3RvY2sgaXRlbXMpLiBGaW5hbGx5LCBlYWNoIHNob3AgbWF5IGNoYXJnZSBhIGZpeGVkIHBlci1vcmRlciBmZWUsIHRoYXQgSm9obiBtdXN0IHBheSBvbmNlLCBpZiBoZSBkZWNpZGVzIHRvIHBsYWNlIGFuIG9yZGVyIGF0IHRoYXQgc2hvcC4gT2YgY291cnNlLCBhIHNpbmdsZSBvcmRlciBjYW4gaW5jbHVkZSBhbnkgbnVtYmVyIG9mIHdpZGdldHMgKHVwIHRvIHRoZSBhbW91bnQgaW4gc3RvY2spLjxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCBiZSBnaXZlbiB0aGUgcHJpY2luZyBpbmZvcm1hdGlvbiBmb3IgYWxsIHNob3BzLiBZb3VyIHRhc2sgaXMgdG8gZGV0ZXJtaW5lIGhvdyBtdWNoIG1vbmV5IEpvaG4gaGFzIHRvIHNwZW5kIHRvIG9idGFpbiB0aGUgZGVzaXJlZCBudW1iZXIgb2Ygd2lkZ2V0cyBpZiBoZSBzcHJlYWRzIGhpcyBvcmRlcnMgb3B0aW1hbGx5IGFjcm9zcyB0aGUgdmFyaW91cyBzaG9wcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgbiAoMSAmbGU7IG4gJmxlOyAxMCAwMDApIGFuZCBtICgxICZsZTsgbSAmbGU7IDEwMCk6IHRoZSBudW1iZXIgb2YgaXRlbXMgdG8gYnV5IGFuZCB0aGUgbnVtYmVyIG9mIHNob3BzIGF2YWlsYWJsZS48XC9saT5cclxuXHQ8bGk+bSBsaW5lcyB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBzPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IHM8c3ViPmk8XC9zdWI+ICZsZTsgMTAgMDAwKSwgcDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBwPHN1Yj5pPFwvc3ViPiAmbGU7IDEwIDAwMCkgYW5kIG88c3ViPmk8XC9zdWI+ICgwICZsZTsgbzxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDApOiB0aGUgbnVtYmVyIG9mIGl0ZW1zIGluIHN0b2NrLCB0aGUgcHJpY2UgcGVyIGl0ZW0gYW5kIHRoZSBwcmljZSBwZXIgb3JkZXIsIGZvciBlYWNoIHNob3AuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIGRlc2lyZWQgbnVtYmVyIG9mIGl0ZW1zIGRvZXMgbm90IGV4Y2VlZCB0aGUgdG90YWwgbnVtYmVyIG9mIGl0ZW1zIGF2YWlsYWJsZSBpbiBhbGwgc2hvcHMgY29tYmluZWQgKGkuZS4gbiAmbGU7ICZTaWdtYTtzPHN1Yj5pPFwvc3ViPikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXI6IHRoZSBtaW5pbXVtIHBvc3NpYmxlIHRvdGFsIGFtb3VudCBvZiBtb25leSBKb2huIG5lZWRzIHRvIHNwZW5kIHRvIG9idGFpbiBuIHdpZGdldHMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=