Problem C
Fog Catchers

Image by Nicole Saffie (Wikimedia Commons), CC BY-SA 2.0

For many people, the word “Peru” conjures up images of the Inca temple Machu Picchu and llamas. But for some visitors to the country, even more remarkable is the sight of fog-catching nets, or atrapanieblas, that Peru is using to harvest water from dense fogs. These nets capture tiny droplets from the fogs, and the water trickles down pipes into troughs that are used to irrigate crops and from which livestock drink. Well, not only livestock — the fog water is an ingredient in a local beer brand, too. According to The Economist, as early as the 1990s, some villages were capturing as much as $8\, 000$ litres of water daily. Today, certain regions in Peru are capable of producing $1\, 400$ litres per second, if the infrastructure is fully deployed.

Now, the weather-simulation consultancy that was hired by the Peruvian government has delivered a model of the fogs that roll in from the sea each day. Everything in the model is positioned relative to an $x$-$y$ coordinate system, with the $x$-axis at ground level, running roughly parallel to the coast (just a few miles inland), and the $y$-axis oriented straight up. According to the model, there are $n$ originator fogs, $F_1, F_2, \ldots , F_ n$. When $F_ i$ rolls in for the first time on day $d_ i$, it settles into a space that intersects the $x$-$y$ plane in an axis-aligned rectangular region with left coordinate $\ell _ i$, right coordinate $r_ i$, and height $h_ i$ — that is, the rectangular region $[\ell _ i, r_ i] \times [0, h_ i]$. Because of the periodic nature of the sea currents, each originator fog $F_ i$ gives rise to $m_ i$ fogs in total (including $F_ i$ itself), the $k$-th of which intersects the rectangular region $[\ell _ i + k\Delta x_ i, r_ i + k\Delta x_ i] \times [0, h_ i + k\Delta h_ i]$ on day $d_ i + k \Delta d_ i$, for $0 \leq k < m_ i$ (where the “change” values $\Delta x_ i$, $\Delta h_ i$, and $\Delta d_ i$ are specific to $F_ i$).

The nets that are erected to catch the fogs are also modelled as axis-aligned rectangular regions lying in the same $x$-$y$ plane (but not necessarily with lower height $0$, as is the case for the fogs). Since building a single rectangular net of sufficient length and height to catch all possible fogs would be prohibitively expensive, it was decided that for the best use of public money, the nets would be installed incrementally. Initially (i.e., on day $0$), there are no nets. Each day, after all the fogs have lifted, net maintainers determine how many fogs were “missed” that day – that is, how many fogs corresponded to rectangles that were not completely contained in the region of the $x$-$y$ plane covered by nets. The workers then add rectangular net “patches” of minimum total area so that the resulting array of nets would have caught all the fogs that day. The next day, the fogs roll in again, they lift, the workers add more patches (if necessary), and the cycle continues. Note that the portion of the $x$-$y$ plane covered by nets at any point in time is a union of axis-aligned rectangles, but in general does not constitute a single rectangular region.

Given a complete description of the $n$ originator fogs, count the total number of fogs that are missed.

Input

The first line of input contains a positive integer $n$ $(n \leq 1\, 000)$, the number of originator fogs. This is followed by $n$ lines, the $i$-th of which contains the parameters of $F_ i$ as eight space-separated integers in this order:

${m_ i}$

– the number of fogs generated by $F_ i$

${d_ i}$

– the day $F_ i$ appears for the first time

${\ell _ i}$

– the leftmost $x$-coordinate of $F_ i$

${r_ i}$

– the rightmost $x$-coordinate of $F_ i$

${h_ i}$

– the height of $F_ i$

$\Delta d_ i$

– the number of days between consecutive fogs generated by $F_ i$

$\Delta x_ i$

– the distance to which each subsequent fog generated by $F_ i$ shifts to the right (if $\Delta x_ i$ is negative, the shift is to the left)

$\Delta h_ i$

– the change in height of each subsequent fog generated by $F_ i$

You can assume that

• $1 \leq m_ i \leq 100$

• $0 \leq d_ i \leq 10^8$

• $-10^8 \leq \ell _ i < r_ i \leq 10^8$

• $1 \leq h_ i \leq 10^8$

• $1 \leq \Delta d_ i \leq 10^6$

• $-10^6 \leq \Delta x_ i, \Delta h_ i \leq 10^6$

• $h_ i + (m_ i-1)\Delta h_ i \geq 1$

Output

Output a single integer, the total number of fogs that are missed.

2
2 3 0 2 9 2 3 0
1 6 1 4 6 3 -1 -2

3

3
4 0 0 10 10 1 15 0
3 5 50 55 8 1 -16 2
3 10 7 10 4 1 8 -1

6

2
7 0 0 20 10 3 0 10
10 1 0 2 5 2 2 7

11

7
8 317 17 21 1000000 59872 5 100000
1 419421 21 22 324455 59872 1 -30993
2 359549 50 51 390820 59872 0 -18659
7 60189 50 51 276352 59872 0 31787
1 419421 50 51 307591 59872 0 10826
1 419421 50 51 492473 59872 0 45464
1 419421 50 51 319158 59872 0 -47232

15