Problem
N명의 사람들이 새 뮤지컬의 시사회 티켓을 사려고 줄을 섰고, 각자 티켓 한 장을 사고 싶어했습니다. 전체 대기열에 대해 하나의 매표소 만 작동했기 때문에 티켓 판매가 매우 느려 "손님"이 생겼습니다. 절망에 빠진 줄. 가장 똑똑한 사람들은 일반적으로 계산원이 같은 티켓을 한 번에 하나씩 판매할 때보다 계산원이 한 손으로 여러 장의 티켓을 더 빨리 판매한다는 사실을 금방 알아차렸습니다.
그래서 그들은 여러 사람이 일렬로 서서 첫 번째 사람에게 돈을 주어 모든 사람을 위한 티켓을 사도록 제안했습니다.
하지만 투기꾼들과 싸우기 위해 출납원은 1인당 3장 이하의 티켓을 팔았기 때문에 이런 식으로 합의에 도달할 수 있는 사람은 2~3명뿐이었습니다.
계산원은 대기열에 있는 i번째 사람에게 티켓 한 장을 판매하는 데 Ai초를 소비하고 Bi 두 장의 티켓, 세 장의 티켓을 판매하는 데 걸리는 초 - Ci 초. 모든 고객에게 서비스를 제공할 수 있는 최소 시간을 계산하는 프로그램을 작성하세요.
단결된 사람들의 그룹 티켓은 항상 첫 번째 사람이 구매한다는 점에 유의하세요. 또한 아무도 속도를 높이기 위해 추가 티켓(아무도 필요로 하지 않는 티켓)을 구매하지 않습니다.
입력:
- 첫 번째 줄에는 숫자 N이 포함됩니다. - 대기열에 있는 구매자 수(\(1<=N<=5000\)) ;
- 다음은 자연수 Ai, Bi의 세 배 N입니다. , Ci. 각 숫자는 3600을 초과하지 않습니다. 대기열에 있는 사람들은 계산원부터 번호가 매겨집니다.
출력: 모든 고객에게 서비스를 제공할 수 있는 최소 시간(초)인 단일 숫자를 인쇄합니다.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
|
12 |
| 2 |
<사업부>2
3 4 5
1 1 1
|
4 |