주식
면접 대비시간 제한1초메모리 제한1024 MB
i번째 날에 주식 xi주를 받고 최대 mi주를 가격 pi에 팔 수 있으며, 팔지 않은 주식은 n일 뒤에 가치가 0이 된다. 얻을 수 있는 최대 이익을 구한다.
문제
Optiver는 수년간의 연구 끝에 기업의 성공 여부를 예측하는 수학적 모델을 개발했다. 이 모델은 주식 시장에서 Optiver에게 큰 이점을 준다.
과거에 Optiver는 한 대기업과 계약을 맺었고, 그 계약에 따라 정해진 일정대로 그 기업의 주식을 사들여야 한다. 그런데 Optiver의 모델에 따르면 그 기업은 정확히 n일 뒤에 파산하며, 그때 주식은 가치가 없어진다.
다행히도 Optiver는 기업이 파산하기 전에 주식을 팔 수 있는 대량의 매도 옵션을 보유하고 있다. 하지만 하루에 팔 수 있는 주식 수에는 한도가 있고, 주식 한 주당 받는 가격은 날마다 다를 수 있다. 따라서 이익을 최대화하려면 언제 주식을 팔아야 하는지 즉시 판단하기 어렵다. Optiver는 이 문제를 계산하는 프로그램을 작성해 달라고 요청했다.
입력
첫째 줄에 정수 t (1 ≤ t ≤ 100)가 주어진다. 이는 테스트 케이스의 수이다. 각 테스트 케이스는 다음과 같다.
- 정수 n (1 ≤ n ≤ 100 000)이 적힌 한 줄: 기업이 파산하기까지 남은 일수이다.
- 세 정수 xi (0 ≤ xi ≤ 100), pi (0 ≤ pi ≤ 100), mi (0 ≤ mi ≤ 10 000 000)가 적힌 n개의 줄: 각각 i일째에 Optiver가 받는 주식 수, i일째 주식 한 주당 (매도) 가격, i일째 Optiver가 팔 수 있는 주식의 최대 수이다.
출력
각 테스트 케이스마다:
- Optiver가 얻을 수 있는 최대 이익을 한 줄에 출력한다.