Problem G
Gelatinous Gladiator

Artwork by Anindya Shiddhartha, mirrored

The small town of Gooville has gotten into a sticky situation. The only road to the outside world is through a narrow strait, and it has been infested with slimes!

Glenn, the village hero, has decided to step up and save the day. He will fight them all alone with his broadsword.

Now, contrary to what basically every RPG out there says, slimes aren’t actually dangerous in the real world. But they are a nuisance, as they will still “attack” you. All slimes are of a specific size $s$, and whenever a size $s$ slime “attacks” you, you end up being covered by $u_ s$ units of slime. While you’re covered with slime, you can’t really do anything but remove it, and it takes one second to remove one unit of slime.

To make matters worse, a group of slimes will all “attack” at the same time. Fortunately, for reasons not yet known to scientists, they will keep you alone if you are covered by any amount of slime. Perhaps they think you are one of them while you’re covered in it?

Whatever the reason, Glenn has concocted a plan with this in mind. The plan is as follows:

1. Slice up to $a_ s$ slimes of one particular size $s$

2. Get “attacked” by all the remaining slimes

3. Remove all the slime

4. If any are left, goto $1$

Whenever Glenn slices up a slime of size $s$, the slime splits into $k_ s$ slimes of size $s-1$. The only exception are slimes of size $1$, which will always turn into inanimate puddles of slime.

But Glenn doesn’t want to take too long: The town really loves garlic and ginger, and they will soon run out. Can you help Glenn clean up the slimes as fast as possible?

Input

The first line contains one integer $S$, the maximum size of a slime. Then follow $S$ lines, one for each size of slime, starting from $1$ going up. All of the lines contain four integers $I_ s$, $k_ s$, $u_ s$ and $a_ s$:

• $I_ s$ is the number of initial $s$-sized slimes

• $k_ s$ is the number of $(s-1)$-sized slimes a $s$-sized slime will turn into when sliced up

• $u_ s$ is the amount of slime a single $s$-sized slime will cover Glenn with per “attack”

• $a_ s$ is the maximum amount of $s$-sized slimes Glenn can split in a single slice

Output

Assuming Glenn uses $1$ second per slice, output the smallest time (in seconds) Glenn would be able to remove all the slimes.

Limits

• $0 < S < 5$

• $0 \leq I_ i \leq i$

• $k_1 = 0$, and for $1 < i$, $0 \leq k_ i \leq i$

• $0 \leq u_ i \leq 100$

• $1 \leq a_ i \leq 100$

Sample Explanation

The optimal choice for Glenn in the first sample is to take each turn as follows:

1. Slice the slime of size $3$. It will split into two, and both will spew $3$ units of slime on Glenn, making this turn take a total of $1 + 2\times 3 = 7$ seconds.

2. Next, Glenn slices the two slimes of size $2$ down to four slimes of size $1$. They will all spew $2$ units of slime on Glenn, making this turn take $1 + 4\times 2 = 9$ seconds.

3. Glenn will now finish off as many slimes of size $1$. He can remove at most $3$, meaning there is only one left. This turn takes $1 + 1\times 2 = 3$ seconds.

4. At the last turn, Glenn finishes off the remaining slime for the time it takes to slice, $1$ second.

3
0 0 2 3
0 2 3 3
1 2 5 3

20

3
1 0 1 2
2 2 3 2
1 2 5 1

48