BOAT

당신은 아주 좋은 배를 한 척 가지고 있다. 여름 동안 이 배를 빌리고 싶다는 요청이 많이 들어오며, 당신은 이익을 최대로 만들고 싶다. 각 손님에 대해, 그 손님이 배를 며칠 동안 빌리고 싶어 하는지와 여러 개의 선택지(choice) 목록을 알고 있다. 하나의 선택지는 금액과 마감일(deadline)로 이루어지며, 마감일은 고정된 기준 시점으로부터 며칠째인지를 나타내는 수이다. 어떤 선택지의 금액은, 그 손님에게 요청한 일수만큼 배를 빌려주되 그 대여가 해당 마감일 이전(또는 당일)에 끝나도록 배치할 수 있을 때에만 받을 수 있다.

예를 들어 친구 Jack은 지중해를 20일 동안 항해하고 싶어 하며 다음과 같은 선택지를 제시한다.

• 마감일이 60일째라면, 20일간의 대여를 0일째와 41일째($60 - 20 + 1$) 사이에 시작하는 경우 1000 EUR를 받는다.
• 마감일이 70일째라면 800 EUR를 받는다.

이익을 최대로 만드는 데 도움이 되지 않는 손님은 받지 않아도 된다. 단, 손님들이 요청을 제출한 순서대로 배를 빌려주어야 한다. 모든 손님과 그들의 선택지가 주어질 때, 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하라.

입력은 텍스트 파일로 주어지며, 하나 이상의 데이터 집합으로 이루어진다. 각 데이터 집합의 형식은 다음과 같다.

• 손님의 수 $n$이 적힌 한 줄 ($n \le 100$).
• $n$개의 줄. $i$번째 줄에는 손님 $i$가 배를 빌리고 싶어 하는 일수(최대 $100$)가 적혀 있다.
• 모든 손님의 선택지 개수의 총합이 적힌 한 줄.
• 각 선택지마다 한 줄씩, client_id deadline amount 형식으로 주어진다. 여기서 client_id는 $1$부터 $n$ 사이의 정수, deadline은 최대 $100$, amount는 음이 아닌 정수이다.

서로 다른 데이터 집합은 빈 줄로 구분된다.

각 데이터 집합에 대해, 그 집합의 최대 이익을 표준 출력에 한 줄로 (줄의 맨 앞부터) 출력한다. 서로 다른 데이터 집합의 결과는 빈 줄로 구분한다.