Chef and Magic Arrays

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Yesterday Chef had cooked N very tasty dishes. A dish is prepared of several ingredients. You are given this information by N arrays, each array contains elements equal to the number of ingredients used in that dish. Also, an element of the array denotes the tastiness of the ingredient in the corresponding dish.
Chef placed his N dishes in a line, one after the other. You can make a simple observation that the last ingredient of a dish will be a neighbor of the first ingredient of the next dish. Of course, this is not valid for the Nth dish, as it's the last dish.
Overall quality of these dishes will be calculated as follows. Consider dish i and i + 1, if the last ingredient of dish i be of tastiness x, and the first ingredient of dish i + 1 of tastiness of y, then the quality of dish will be increased by x  y * i, where (t denotes the absolute value of t).
Chef wants to maximize the quality of the dish. For each dish, he is allowed to take its ingredients and cyclically rotate/shift them by as many rotations as he wishes. Find the maximum possible quality of the dishes that he can obtain.
Input
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains a single integer N denoting the number of dishes.
Next N lines follows. ith line contains integer M denoting the number of ingredients in ith dish and M spaceseparated integers A_{1}, A_{2}, ..., A_{M} denoting the tastiness of ingredients of ith dish.".
Output
For each test case, output in a single line an integer corresponding to the maximum possible quality of the dishes.
Constraints
 Total number of ingredients over all the test cases in a single test file won't exceed 10^{6}
 M ≥ 1
 1 ≤ A_{i} ≤ 10^{6}
Subtasks
 Subtask #1 (20 points): Total number of dishes = 2.
 Subtask #2 (30 points): 1 ≤ A_{i} ≤ 500
 Subtask #3 (50 points): original constraints
Example
Input: 3 3 3 1 2 3 2 3 2 2 4 5 2 2 1 2 2 4 5 3 2 1 2 3 3 2 5 2 4 5 Output: 8 4 10
Explanation
Example case 1. 01) 1233245 = 0 * 1 + 2 * 2 = 4 02) 3123245 = 1 * 1 + 2 * 2 = 5 03) 2313245 = 2 * 1 + 2 * 2 = 6 04) 1232345 = 1 * 1 + 1 * 2 = 3 05) 3122345 = 0 * 1 + 1 * 2 = 2 06) 2312345 = 1 * 1 + 1 * 2 = 3 07) 1233254 = 0 * 1 + 3 * 2 = 6 08) 3123254 = 1 * 1 + 3 * 2 = 7 09) 2313254 = 2 * 1 + 3 * 2 = 8 10) 1232354 = 1 * 1 + 2 * 2 = 5 11) 3122354 = 0 * 1 + 2 * 2 = 4 12) 2312354 = 1 * 1 + 2 * 2 = 5
Author:  berezin 
Tester:  alex_2oo8 
Editorial  https://discuss.codechef.com/problems/MARRAYS 
Tags  berezin, dynamicprogramming, easymedium, oct17 
Date Added:  23012014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions