나무꾼 잭

면접 대비

시간 제한1초메모리 제한1024 MB

요약

나무 종마다 심은 해와 증가 기간, 초기 개체 수가 주어질 때, 한 해에 베어 낼 수 있는 나무의 최대 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 정렬, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

나무꾼 잭은 예전에 나무 베기를 즐겼다. 잭은 나이가 들면서 한때 좋아하던 이 일에 지쳐 간다. 그는 '더 빅 원'이라는 계획을 떠올리고, 마지막으로 숲에 들어가 나무를 최대한 많이 베어 내고 싶어 한다.

잭은 자기 동네 상록수 숲을 관리하는 산림 관리인에게 전화를 건다. 관리인은 나무 종마다 개체 수가 어떻게 변하는지 알려 준다. 종 $k$ 는 $B_k$ 년에 $S_k$ 그루가 심어진다. 그 뒤 $Y_k$ 년 동안 개체 수는 해마다 $I_k$ 그루씩 늘어난다. $Y_k$ 년이 지나면 해마다 $I_k$ 그루씩 줄어들고, 결국 0이 되어 사라질 수도 있다.

잭은 지금부터 먼 미래까지 어느 한 해에 한꺼번에 베어 낼 수 있는 나무의 최대 수를 알고 싶어 한다. 그가 그때까지 살아 있지 않다면, 그의 후손이 대신 나무를 벤다.

모든 개체 수는 매년 한 번씩 동시에 즉시 변한다고 가정한다. 잭은 매년 변화가 끝난 뒤의 개체 수를 기준으로 판단한다.

입력

입력은 한 개의 테스트 케이스로 이루어진다. 첫째 줄에는 숲에 있는 나무 종의 수 $N$ ( $1 \le N \le 1000$ )이 주어진다.

이어지는 $N$ 개 줄에는 정수 $Y$ , $I$ , $S$ , $B$ 가 차례로 주어진다 ( $0 \le Y \le 1000000$ , $0 \le I \le 1000$ , $0 \le S \le 1000000$ , $0 \le B \le 1000000$ ). 여기서 $S$ 는 처음 심는 개체 수, $B$ 는 심는 해, $Y$ 는 개체 수가 해마다 $I$ 씩 늘어나는 기간(년)이다. 이 기간이 끝나면 개체 수는 해마다 $I$ 씩 줄어들고, 결국 사라질 수도 있다.

출력

어느 한 해에 베어 낼 수 있는 나무의 최대 수를 출력한다.

예제2

예제 1
입력
```
1
10 10 0 5
```
예상 출력
```
100
```
예제 2
입력
```
3
5 10 0 4
10 10 10 1
5 5 0 0
```
예상 출력
```
145
```