Time Limit: 5 sec
Memory Limit: 64 MB
Attempts: 0
Accuracy: 0.00%
Author: Akashdeep Goel

Thank you all for helping us to optimize for the Publicity of Insomnia round one. Now the round two is on and publicity is going weak at this moment. We need your help again.

We have in our locker some bundles of dollar notes in which the notes can be taken out only from one end. If a bundle is opened it is mandatory to empty it out first before touching another bundle. But the things have got twisted recently. We don't know how it happened but last time when I visited the locker I found a magical thing in it that makes the dollar notes grow in value daily by the amount they were in original. For example, a note of value $2 in an unopened bundle becomes $4, $6, $8 .... on day 2,3,4.... respectively. Dollar is also becoming more expensive with respect to Indian currency INR. On day one $1 is equivalent to Rs.1, on day two Rs.2, on day three Rs.3 and so on...........

Now we can take out only one dollar note daily. A dollar note can only be taken from an already opened bundle or from any bundle if there are no bundle currently opened. A dollar note can only be taken out from any end(top or bottom) of a bundle. On taking out a note, the note next to it comes on that end.

Please help us to optimize our publicity.

**Input:**

First line contains n, number of dollar bundles in the locker. Next line contains n space

separated integers (m1, m2, m3, ...... mi ..... mn ), the number of dollar notes in the respective bundle.

Next n line follows each with (mi) space separated integers that denote the vale of

dollar notes in the corresponding bundle on the day one from top to bottom.

**Output:**

Single integer containing the value we can make most for publicity in INR.

**Sample Input:**

3

1 3 2

1

9 8 4

2 3

**Sample Output:**

467

**Sample Input:**

7

5 4 3 8 5 7 3

4 6 3 5 7

1 1 1 1

3 2 1

4 3 6 3 5 6 3 2

3 6 8 5 4

3 4 5 6 4 3 2

6 4 8

**Sample Output:**

68805

**Constraints:**

0<=n<=15.

0<mi<=10

0<Dollar note value<10.

Time for each test case= 1sec.

Total of about 4 test files.

Explanation to I/O sample

In first input sample, the person will choose the bundle in order first, third and then second. In the first bundle there is only one note. He will pick it. Then he will choose third bundle. While he opens up the third bundle, he will get notes of value 4 and 6 in place of 2 and 3 because the value of notes in a closed bundle increases with time by above given method in the question. He will pick in order 4 and the 6. Now he will open bundle second and he will find notes of value 36, 32 and 16. He will pick in order 16,32 then 36. It is notable that when he picks note of value 16 then the ends of the bundle becomes 36 and 32. He can pick any of these two. For optimal picking he will first pick 32 and then 36.

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED