Jimbo

Gimi has recently discovered a new game called Talatro. In this game, Gimi has a deck of $N$ cards, and his goal is to maximize the score obtained by playing exactly $5$ cards.

At the beginning, the score is determined by two components:

• Chips, denoted by $C$, initialized with $0$.
• Multiplier, denoted by $M$, initialized with $1$.

Each card played by Gimi can modify the values of $C$ and $M$. There are $4$ types of cards:

• $1\,\,x\colon$ Adds $x$ to $C$. More precisely, $C \leftarrow C + x$.
• $2\,\,x\,\,y\colon$ Adds $x$ to $C$ and adds $y$ to $M$. More precisely, $C \leftarrow C + x, M \leftarrow M + y$.
• $3\,\,x\,\,z\colon$ Adds $x$ to $C$ and multiplies $M$ by $z$. More precisely, $C \leftarrow C + x, M \leftarrow M \cdot z$.
• $4\,\,x\,\,y\,\,z\colon$ Adds $x$ to $C$, then adds $y$ to $M$, and finally multiplies $M$ by $z$. More precisely, $C \leftarrow C + x, M \leftarrow (M + y) \cdot z$.

The final score is calculated as the product of $C$ and $M$. Gimi is free to choose the order in which he plays the cards. The question is: what is the maximum score he can achieve?

Task

Write a program that, given as input $N$ (the total number of cards in the deck) and the description of the $N$ cards, determines the maximum score Gimi can obtain.

Input Data

The input file contains on the first line the natural number $N$, representing the total number of cards in the deck. The following $N$ lines each describe one card, with each line starting with the value $t_i$, indicating the type of card $i$. Depending on the type of the card, the corresponding values follow:

• For $t_i = 1$, the value $x_i$ is given.
• For $t_i = 2$, the values $x_i$ and $y_i$ are given.
• For $t_i = 3$, the values $x_i$ and $z_i$ are given.
• For $t_i = 4$, the values $x_i, y_i$, and $z_i$ are given.

Output data

The output file will contain on the first line a single natural number, representing the maximum achievable score.

Restrictions

• $5 \leq N \leq 1000$.
• $1 \leq x_i, y_i \leq 1000$, for any $1 \leq i \leq N$.
• $2 \leq z_i \leq 100$, for any $1 \leq i \leq N$.

Example

stdin

6
1 3
1 5
2 1 1
3 1 2
4 1 1 2
3 1 3

stdout

324

Explanation

The optimal playing order is: the cards with indices $2, 3, 5, 4,$ and $6$.
Initially: $C = 0$, $M = 1$.
After card 2: $C = 5, M = 1$
After card 3: $C = 6, M = 2$
After card 5: $C = 7, M = 6$
After card 4: $C = 8, M = 12$
After card 6: $C = 9, M = 36$
Final score: $C \cdot M = 9 \cdot 36 = 324$.
A different order of playing these cards may lead to lower scores.