uCoder | 1358 | Nível: 5 | Tempo Limite: 4
Marblecoin
Adaptado por None
Competição: Maratona de Programação da SBC 2017 - Fase Nacional
Cubiconia is known for having one of the highest tax rates. Taxes are calculated on a daily basis and even things that seem worthless are subject to taxes. In order to avoid the crazy tax rates, some of the emperor’s friends created a new currency using marbles. Unfortunately, it didn’t work out, marbles became subject to taxes as well.
Despite this, the emperor believes that using marbles as a currency is a great idea and that in the future they will be worth a lot more. So he decided to steal all of his friends’ marbles. To avoid unnecessary attention, in the dead of each night he will visit one of his friends and during each visit exactly one marble will be stolen. Since the emperor’s friends keep their marbles in stacks, only a marble that is currently on the top of a stack might be stolen.
Each marble has a value associated to it. The amount due per owned marble is V × 365D, where V is the value associated to the marble and D is the number of days the marble was owned. The emperor plans to sell all the marbles once he is finished stealing them. This means that, if there is a total of T marbles, the marble owned the least amount of time will be owned for 1 day, while the one owned the maximum amount of time will be owned for T days.
The emperor is smart and already realized that the total due in taxes depends on the order in which marbles are stolen. To avoid paying more taxes than necessary, he would like to know the best order to steal the marbles. Can you help him?
Entrada
The first line contains an integer N (1 ≤ N ≤ 105) representing the number of stacks the emperor is going to steal from. Each of the next N lines describes a stack with an integer K (1 ≤ K ≤ 105) followed by K integers V1, V2 , . . . , V K (1 ≤ Vi ≤ 300 for i = 1, 2, . . . , K); the number K is the amount of marbles in the stack, while the numbers V1 , V2 , . . . , VK are the values of the marbles in the stack, from top to bottom. The total amount of marbles is at most 4 × 105.
Saída
Output a single line with an integer representing the minimum value due in taxes if the marbles are stolen in an optimal order. Because this number can be very large, output the remainder of dividing it by 109 + 7.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
3 |
227712621
|
|
3 |
48894670
|