대동제 마지막 날 무대에 올릴 개 팀의 섭외가 확정되었다. 각 팀에는 번부터 번까지 번호가 붙어 있다. 번 팀의 공연 시간은 분이고, 이 팀의 공연을 보려는 관객은 명이다.
학생회는 다음 규칙에 따라 공연을 진행한다.
공연할 팀과 공연 순서를 적절히 정했을 때, 대기 비용과 위약금 합의 최솟값을 구해 보자.
첫째 줄에 공연 팀의 수 이 주어진다. ()
둘째 줄부터 개의 줄에 걸쳐 각 팀의 공연 시간 , 관객 수 , 위약금 가 팀 번호 순서대로 공백으로 구분되어 주어진다. (, , )
대기 비용과 위약금 합의 최솟값을 출력한다.
첫 번째 예제에서는 번 팀의 공연을 취소하고, 번 팀과 번 팀의 순서로 공연하면 된다. 두 공연이 끝나는 시각은 각각 분과 분이므로, 대기 비용과 위약금의 합은 이다.
입력으로 주어지는 모든 수는 정수이다.
두 번째 예제에서는 모든 공연을 취소하면 된다. 위약금의 합은 이다.