Marbles sit in stacks; only top marbles can be taken, one per day, and each marble's tax is value times 365 raised to days owned. Minimize the total tax modulo 1e9+7.
Medium7GreedySortingMathPrefix sumNo attempts yetTime limit1sMemory limit1024 MBCubiconia has one of the highest tax rates anywhere. Taxes are computed daily, and even things that look worthless are taxed. To escape those rates, some of the emperor's friends minted a new currency out of marbles. It did not work. Marbles became taxable as well.
The emperor still thinks marbles make a fine currency and that they will be worth much more later, so he decided to steal every marble his friends own. To avoid attention he visits one friend in the dead of each night and takes exactly one marble per visit. His friends keep their marbles in stacks, so only a marble that currently sits on top of a stack can be stolen.
Every marble has a value. The tax due for one marble is V×365D, where V is the value of the marble and D is the number of days it was owned. The emperor plans to sell all the marbles once he is done stealing them. If there are T marbles in total, the marble he steals last is owned for 1 day and the marble he steals first is owned for T days.
The total tax depends on the order in which the marbles are stolen. Compute the total tax for the order that pays the least.
The first line contains an integer N (1≤N≤105), the number of stacks the emperor is going to steal from. Each of the next N lines describes one stack. The line starts with the number of marbles in that stack, K (1≤K≤105), followed by the values of the marbles V1,V2,…,VK (1≤Vi≤300) from top to bottom. The total number of marbles is at most 4×105.
Print one line with the minimum tax due when the marbles are stolen in an optimal order, modulo 109+7.