Jack The Lumberjack

Interview

Time limit1sMemory limit1024 MB

Summary

Given N tree species that are planted, grow linearly for Y years, then shrink, find the maximum total number of trees alive in any single year.

Level: Medium5 of 10
Topics: Sorting, Simulation, Implementation
Solved: No attempts yet

Problem

Jack the Lumberjack used to love chopping down trees. Jack is getting older and is tired of the activity he once loved. He has an idea, 'The Big One', and wants to go into the forest one last time to harvest as many trees as possible.

Jack calls the forest administrator for his local evergreen forest. The administrator explains how the population changes for each tree species. For each species $k$ , $S_k$ trees are planted in year $B_k$ . For the next $Y_k$ years, the population increases by $I_k$ per year. After $Y_k$ years, it decreases by $I_k$ per year until it possibly dies out.

Jack wants to find the maximum number of trees that could be harvested at once, from now until the distant future. If he is no longer around to do it, his descendants will be.

Assume all populations change instantly and at the same time, once per year. Jack assesses each population's size after the yearly change occurs.

Input

The input contains a single test case. The first line contains an integer $N$ ( $1 \le N \le 1000$ ), the number of tree species in the forest.

Each of the following $N$ lines contains four integers $Y$ , $I$ , $S$ , $B$ ( $0 \le Y \le 1000000$ , $0 \le I \le 1000$ , $0 \le S \le 1000000$ , $0 \le B \le 1000000$ ). Here $S$ is the starting population size, $B$ is the year in which the population is planted, and $Y$ is the number of years during which the population increases by $I$ each year before it decreases by $I$ each year until it possibly dies out.

Output

Print the maximum number of trees that can be harvested in any single year.

Examples2

Example 1
Input
```
1
10 10 0 5
```
Expected output
```
100
```
Example 2
Input
```
3
5 10 0 4
10 10 10 1
5 5 0 0
```
Expected output
```
145
```