J. Splendor
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little S really likes playing board games, especially Splendor. Now he has simplified and modified the rules.

The game includes the following components:

  • Chips: There are $$$5$$$ colors, numbered $$$1, 2, 3, 4, 5$$$, and the number of chips of each color can be considered infinite.
  • Cards: There are $$$n$$$ cards, stacked in order to form a deck, with the cards numbered $$$1, 2, \dots, n$$$. Each card $$$i$$$ has a color $$$c_i$$$ ($$$1 \le c_i \le 5$$$) and the quantities of the five types of chips required for exchange: $$$p_{i,1}$$$, $$$p_{i,2}$$$, $$$p_{i,3}$$$, $$$p_{i,4}$$$, and $$$p_{i,5}$$$.

At the beginning of the game, the top $$$4$$$ cards (cards $$$1$$$ to $$$4$$$) of the deck are revealed on the table to serve as the initial exchangeable cards. The remaining cards in the deck are now cards $$$5$$$ through $$$n$$$.

In each turn, you may perform exactly one of the following three operations:

  1. Choose one color and take $$$2$$$ chips of that color;
  2. Choose three different colors and take $$$1$$$ chip of each chosen color;
  3. Choose a card $$$i$$$ from the exchangeable cards on the table, pay the corresponding chips, and exchange it. When you exchange card $$$i$$$, the number of chips of each color $$$k$$$ required is subject to a discount based on the previously exchanged cards: If you have previously exchanged $$$d_k$$$ cards of color $$$k$$$, then when exchanging the current card, the actual number of chips of color $$$k$$$ required is $$$\max(0, p_{i,k} - d_k)$$$.

Whenever you successfully exchange an exchangeable card on the table:

  1. Remove the card from the table;
  2. If there are still face-down cards in the deck, draw $$$1$$$ card from the top of the deck in order and place it on the table as an exchangeable card;
  3. Clear all remaining chips from your current hand (note that this rule differs from the original rules).

Your goal is to empty the deck. Note that there may still be some exchangeable cards left on the table at this point; this situation is also considered a successful completion of the goal. Please calculate the minimum number of turns required to achieve this goal.

Input

The first line contains an integer $$$n$$$ ($$$4\le n\le 100$$$).

For the next $$$n$$$ lines, the $$$i$$$-th line contains $$$6$$$ integers, respectively $$$c_i$$$, $$$p_{i,1}$$$, $$$p_{i,2}$$$, $$$p_{i,3}$$$, $$$p_{i,4}$$$, $$$p_{i,5}$$$ ($$$1 \le c_i \le 5$$$, $$$0 \le p_{i,j} \le 10^9$$$), indicating the color of the $$$i$$$-th card and the number of chips required.

Output

Output an integer representing the minimum number of turns.

Examples
Input
5
1 4 1 1 7 1
1 2 2 8 4 8
1 2 3 6 7 2
1 6 5 7 3 1
1 9 9 9 9 9
Output
7
Input
7
2 15 34 0 15 24
4 11 20 0 18 0
1 4 0 2 48 20
3 17 0 8 43 70
1 0 58 7 1 52
1 64 0 81 40 0
2 4 0 0 0 10
Output
86
Note

For the first example: For the first four cards, it takes $$$6$$$, $$$8$$$, $$$7$$$, and $$$8$$$ operations, respectively, to accumulate the required number of chips through chip-taking operations.

The optimal strategy is: First, spend $$$6$$$ moves to collect chips to meet the requirement of the first card, then use the $$$7$$$-th move to "exchange cards". After the exchange is complete, the $$$5$$$-th card (the last one) in the deck is placed on the table, at which point the deck is empty. This takes a total of $$$7$$$ moves.

The specific steps are as follows:

  1. Take $$$1$$$ chip each of colors $$$1$$$, $$$4$$$, and $$$5$$$.
  2. Take $$$1$$$ chip each of colors $$$1$$$, $$$3$$$, and $$$4$$$.
  3. Take $$$1$$$ chip each of colors $$$1$$$, $$$4$$$, and $$$5$$$.
  4. Take $$$1$$$ chip each of colors $$$2$$$, $$$4$$$, and $$$5$$$.
  5. Take $$$1$$$ chip each of colors $$$1$$$, $$$2$$$, and $$$4$$$.
  6. Take $$$2$$$ chips of color $$$4$$$. After the first $$$6$$$ rounds, the number of chips in hand is: $$$4$$$ of color $$$1$$$, $$$2$$$ of color $$$2$$$, $$$1$$$ of color $$$3$$$, $$$7$$$ of color $$$4$$$, and $$$3$$$ of color $$$5$$$, which is sufficient to pay the chip requirements for the first card ($$$4, 1, 1, 7, 1$$$).
  7. Select the first card, pay the corresponding chips, and exchange it. After the exchange is complete, the $$$5$$$-th card (the last one) from the deck is placed on the table, at which point the deck is empty. The goal is achieved in a total of $$$7$$$ rounds.