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 N-th 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. i-th line contains integer M denoting the number of ingredients in i-th dish and M space-separated integers A_{1}, A_{2}, ..., A_{M} denoting the tastiness of ingredients of i-th 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) 123|32|45 = 0 * 1 + 2 * 2 = 4
02) 312|32|45 = 1 * 1 + 2 * 2 = 5
03) 231|32|45 = 2 * 1 + 2 * 2 = 6
04) 123|23|45 = 1 * 1 + 1 * 2 = 3
05) 312|23|45 = 0 * 1 + 1 * 2 = 2
06) 231|23|45 = 1 * 1 + 1 * 2 = 3
07) 123|32|54 = 0 * 1 + 3 * 2 = 6
08) 312|32|54 = 1 * 1 + 3 * 2 = 7 
09) 231|32|54 = 2 * 1 + 3 * 2 = 8
10) 123|23|54 = 1 * 1 + 2 * 2 = 5
11) 312|23|54 = 0 * 1 + 2 * 2 = 4
12) 231|23|54 = 1 * 1 + 2 * 2 = 5

Difficulty: HARD
Tags: Sorting

Range queries

Segment trees revisited

Complete search

Dynamic programming

Data structures
Skill types: Sorting

Range queries

Complete search

Dynamic programming

Data structures

Starter code:

Solutions:
inf = 10000000
t = int(input())
for _ in range(t):
	dp = []
	a = []
	m = []
	n = int(input())
	for _ in range(n):
		inp = list(map(int, input().split()))
		a.append(inp[1:])
		m.append(inp[0])
		dp.append([0] * inp[0])
	for i in range(1, n):
		(m1, m2) = (-inf, -inf)
		for j in range(m[i - 1]):
			m1 = max(m1, dp[i - 1][(j + 1) % m[i - 1]] - i * a[i - 1][j])
			m2 = max(m2, dp[i - 1][(j + 1) % m[i - 1]] + i * a[i - 1][j])
		for j in range(m[i]):
			dp[i][j] = max(dp[i][j], m1 + i * a[i][j], m2 - i * a[i][j])
	ans = max(dp[n - 1])
	print(ans)


def shift_array_by_one(a):
	return [a.pop(-1)] + a
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	for i in range(n):
		inp = list(map(int, input().strip().split()))
		cnt = inp.pop(0)
		if i == 0:
			new_cost = [0] * cnt
		else:
			new_cost = []
			for j in range(cnt):
				elem = i * inp[j]
				val = max(m1 + elem, m2 - elem)
				new_cost.append(val)
		last_dishes = shift_array_by_one(inp)
		m1 = new_cost[0] - (i + 1) * last_dishes[0]
		m2 = new_cost[0] + (i + 1) * last_dishes[0]
		for k in range(1, cnt):
			valp = new_cost[k] - (i + 1) * last_dishes[k]
			valn = new_cost[k] + (i + 1) * last_dishes[k]
			if valp > m1:
				m1 = valp
			if valn > m2:
				m2 = valn
	print(max(new_cost))


INF = 10 ** 15
for t in range(int(input())):
	N = int(input())
	A = [list(map(int, input().split()))[1:] for i in range(N)]
	M = [len(Ai) for Ai in A]
	dp_firstpos = [-INF] * N
	dp_firstneg = [-INF] * N
	dp_firstpos[N - 1] = max(A[N - 1]) * (N - 1)
	dp_firstneg[N - 1] = -min(A[N - 1]) * (N - 1)
	for i in range(N - 2, -1, -1):
		for j in range(M[i]):
			lastpos = A[i][j - 1] * (i + 1) + dp_firstneg[i + 1]
			lastneg = -A[i][j - 1] * (i + 1) + dp_firstpos[i + 1]
			firstpos = A[i][j] * i
			firstneg = -A[i][j] * i
			dp_firstpos[i] = max(dp_firstpos[i], firstpos + lastpos, firstpos + lastneg)
			dp_firstneg[i] = max(dp_firstneg[i], firstneg + lastpos, firstneg + lastneg)
	ans = max(dp_firstpos[0], dp_firstneg[0])
	print(ans)


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = []
		for _ in range(N):
			A.append(list(map(int, input().split()[1:])))
		P = M = 0
		for i in range(N):
			li = len(A[i])
			P0 = max((max(P - i * A[i][j] + (i + 1) % N * A[i][(j - 1) % li], M + i * A[i][j] + (i + 1) % N * A[i][(j - 1) % li]) for j in range(li)))
			M0 = max((max(P - i * A[i][j] - (i + 1) % N * A[i][(j - 1) % li], M + i * A[i][j] - (i + 1) % N * A[i][(j - 1) % li]) for j in range(li)))
			(P, M) = (P0, M0)
		print(P)
main()


INF = 10 ** 15
for t in range(int(input())):
	N = int(input())
	A = [list(map(int, input().split()))[1:] for i in range(N)]
	M = [len(Ai) for Ai in A]
	dp = [[-INF] * 4 for i in range(N)]
	dp[N - 1][0] = max(A[N - 1]) * (N - 1)
	dp[N - 1][1] = -min(A[N - 1]) * (N - 1)
	for i in range(N - 2, -1, -1):
		for j in range(M[i]):
			pos = A[i][j - 1] * (i + 1) + dp[i + 1][1]
			neg = -A[i][j - 1] * (i + 1) + dp[i + 1][0]
			dp[i][0] = max(dp[i][0], pos + A[i][j] * i, neg + A[i][j] * i)
			dp[i][1] = max(dp[i][1], pos - A[i][j] * i, neg - A[i][j] * i)
	ans = max(dp[0])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for i in range(n):
		b = list(map(int, input().strip().split()))
		a.append(b)
	m = []
	ans = []
	for i in range(n):
		min = 1
		max = 1
		for j in range(1, a[i][0] + 1):
			if a[i][j] < a[i][min]:
				min = j
			if a[i][j] > a[i][max]:
				max = j
		m.append((min, max))
	if n == 1:
		print(0)
		continue
	ans1 = []
	ans2 = []
	for i in range(1, a[1][0] + 1):
		ans1.append(abs(a[0][m[0][0]] - a[1][i]))
		ans2.append(abs(a[0][m[0][1]] - a[1][i]))
	for i in range(n - 2):
		maxp1 = 0
		maxp2 = 0
		max1 = ans1[0] + abs(a[i + 1][a[i + 1][0]] - a[i + 2][m[i + 2][0]]) * (i + 2)
		max2 = ans1[0] + abs(a[i + 1][a[i + 1][0]] - a[i + 2][m[i + 2][1]]) * (i + 2)
		for j in range(a[i + 1][0]):
			if max1 < ans1[j] + abs(a[i + 1][(j - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][m[i + 2][0]]) * (i + 2):
				maxp1 = j
				max1 = ans1[maxp1] + abs(a[i + 1][(maxp1 - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][m[i + 2][0]]) * (i + 2)
			if max2 < ans1[j] + abs(a[i + 1][(j - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][m[i + 2][1]]) * (i + 2):
				maxp2 = j
				max2 = ans1[maxp2] + abs(a[i + 1][(maxp2 - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][m[i + 2][1]]) * (i + 2)
		ans = []
		for j in range(1, a[i + 2][0] + 1):
			k1 = ans1[maxp1] + abs(a[i + 1][(maxp1 - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][j]) * (i + 2)
			k2 = ans1[maxp2] + abs(a[i + 1][(maxp2 - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][j]) * (i + 2)
			if k2 > k1:
				ans.append(k2)
			else:
				ans.append(k1)
		ans1 = ans
		maxp1 = 0
		maxp2 = 0
		max1 = ans2[0] + abs(a[i + 1][a[i + 1][0]] - a[i + 2][m[i + 2][0]]) * (i + 2)
		max2 = ans2[0] + abs(a[i + 1][a[i + 1][0]] - a[i + 2][m[i + 2][1]]) * (i + 2)
		for j in range(a[i + 1][0]):
			if max1 < ans2[j] + abs(a[i + 1][(j - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][m[i + 2][0]]) * (i + 2):
				maxp1 = j
				max1 = ans2[maxp1] + abs(a[i + 1][(maxp1 - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][m[i + 2][0]]) * (i + 2)
			if max2 < ans2[j] + abs(a[i + 1][(j - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][m[i + 2][1]]) * (i + 2):
				maxp2 = j
				max2 = ans2[maxp2] + abs(a[i + 1][(maxp2 - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][m[i + 2][1]]) * (i + 2)
		ans = []
		for j in range(1, a[i + 2][0] + 1):
			k1 = ans2[maxp1] + abs(a[i + 1][(maxp1 - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][j]) * (i + 2)
			k2 = ans2[maxp2] + abs(a[i + 1][(maxp2 - 1 + a[i + 1][0]) % a[i + 1][0] + 1] - a[i + 2][j]) * (i + 2)
			if k2 > k1:
				k1 = k2
			ans.append(k1)
		ans2 = ans
	ansx = -1
	for i in ans1:
		if i > ansx:
			ansx = i
	for i in ans2:
		if i > ansx:
			ansx = i
	print(ansx)


import sys

class Dish:

	def __init__(self, arr, ind):
		self.arr = arr
		if ind == 1 or ind == n:
			min1 = min(arr)
			max1 = max(arr)
			self.arr = [min1, max1]
		self.len = len(self.arr)
		self.arrVal = [0] * self.len
		self.ind = ind
		self.prods1 = []
		self.prods2 = []
		self.valInd = 0

	def rebuildArr(self):
		arr = self.arr
		arrVal = self.arrVal
		ar1 = []
		ar2 = []
		for ind in range(self.len):
			next1 = arrVal[ind] + self.ind * arr[ind]
			next2 = arrVal[ind] - self.ind * arr[ind]
			ar1.append((next1, ind))
			ar2.append((next2, ind))
		ar1.sort()
		ar2.sort()
		ind1 = ar1[-1][1]
		ind2 = ar2[-1][1]
		self.arr = [self.arr[ind1], self.arr[ind2]]
		self.arrVal = [self.arrVal[ind1], self.arrVal[ind2]]
		self.len = 2

	def __str__(self):
		return str((self.ind, len(self.arr), self.vals))

	def getCur(self):
		(first, last) = self.vals[self.valInd]
		return first

	def getLast(self):
		(first, last) = self.vals[self.valInd]
		return last

	def initProds(self):
		if self.ind == 1 or self.ind == n:
			minVal = min(self.arr)
			maxVal = max(self.arr)
			self.prods1.append((minVal, minVal, minVal))
			self.prods2.append((maxVal, maxVal, maxVal))
			self.prods1.sort()
			self.prods2.sort()
			return
		for i in range(self.len):
			j = (i - 1 + self.len) % self.len
			I = self.arr[i]
			J = self.arr[j]
			next1 = self.ind * I * (self.ind + 1) * J
			next2 = self.ind * I / ((self.ind + 1) * J)
			self.prods1.append((next1, I, J))
			self.prods2.append((next2, I, J))
		self.prods1.sort()
		self.prods2.sort()

	def getVals(self):
		res = set([])
		res.add(self.prods1[0][1:])
		res.add(self.prods2[0][1:])
		res.add(self.prods1[-1][1:])
		res.add(self.prods2[-1][1:])
		return list(res)

def doMaxOne(ind):
	global dishes, n
	dish = dishes[ind]
	curPower = getPower(ind)
	curValInd = dish.valInd
	for rec in range(len(dish.vals)):
		dish.valInd = rec
		power1 = getPower(ind)
		power2 = 0
		if rec > 0:
			power2 = getPower(ind - 1)
		power = power1 + power2
		if power > curPower:
			curValInd = rec
			curPower = power
	dish.valInd = curValInd

def doMaxTwo():
	for rec in range(len(dishes) - 1):
		dish1 = dishes[rec]
		dish2 = dishes[rec + 1]
		curRec1 = 0
		curRec2 = 0
		curProd = 0
		for val1Ind in range(len(dish1.vals)):
			val1 = dish1.vals[val1Ind]
			dish1.valInd = val1Ind
			for val2Ind in range(len(dish2.vals)):
				val2 = dish2.vals[val2Ind]
				dish2.valInd = val2Ind
				nextProd = getPower(rec) + getPower(rec + 1)
				if nextProd > curProd:
					curRec1 = val1Ind
					curRec2 = val2Ind
					curProd = nextProd
		dish1.valInd = curRec1
		dish2.valInd = curRec2

def doMaxThree():
	if n < 3:
		doMaxTwo()
		return
	for rec in range(len(dishes) - 2):
		dish1 = dishes[rec]
		dish2 = dishes[rec + 1]
		dish3 = dishes[rec + 2]
		curRec1 = 0
		curRec2 = 0
		curRec3 = 0
		curProd = 0
		for val1Ind in range(len(dish1.vals)):
			val1 = dish1.vals[val1Ind]
			dish1.valInd = val1Ind
			for val2Ind in range(len(dish2.vals)):
				val2 = dish2.vals[val2Ind]
				dish2.valInd = val2Ind
				for val3Ind in range(len(dish3.vals)):
					val3 = dish3.vals[val3Ind]
					dish3.valInd = val3Ind
					nextProd = getPower(rec) + getPower(rec + 1) + getPower(rec + 2)
					if nextProd > curProd:
						curRec1 = val1Ind
						curRec2 = val2Ind
						curRec3 = val3Ind
						curProd = nextProd
		dish1.valInd = curRec1
		dish2.valInd = curRec2
		dish3.valInd = curRec3

def calcPower():
	res = 0
	for ind in range(len(dishes)):
		res += getPower(ind)
	return res

def doit():
	for ind in range(len(dishes)):
		doMaxOne(ind)

def printDishes():
	for dish in dishes:
		print(dish.vals[dish.valInd])
		print(dish.vals)

def getPower(ind):
	if ind == n - 1:
		return 0
	last = dishes[ind].getLast()
	first = dishes[ind + 1].getCur()
	return abs(last - first) * dishes[ind].ind

def bruteForce():
	for dishInd in range(1, n):
		dish = dishes[dishInd]
		prevDish = dishes[dishInd - 1]
		ln = dish.len
		for arrInd in range(dish.len):
			ingr = dish.arr[arrInd]
			curInd = -1
			curVal = 0
			for prevInd in range(prevDish.len):
				nextVal = prevDish.arrVal[prevInd] + abs(prevDish.arr[prevInd] - ingr) * dishInd
				if nextVal > curVal:
					curVal = nextVal
			dish.arrVal[(arrInd - 1 + ln) % ln] = curVal
		dish.rebuildArr()
	return max(dishes[n - 1].arrVal)
q = int(input().strip())
for _ in range(q):
	dishes = []
	n = int(input().strip())
	for ind in range(n):
		dishes.append(Dish(list(map(int, input().strip().split(' ')))[1:], ind + 1))
	print(bruteForce())


import bisect
MIN = -10 ** 20

def read_test():
	N = int(input())
	A = []
	for _ in range(N):
		A.append(list(map(int, input().strip().split()))[1:])
	return (N, A)

def solve_test(N, A):
	sol = 0
	(P, Q) = ([], [])
	(mx_pre, mx_suf) = ([], [])

	def process_min_max():
		nonlocal P, mx_pre, mx_suf
		lP = len(P)
		mx_pre = [MIN] * lP
		mx_suf = [MIN] * lP
		for i in range(lP):
			mx_pre[i] = max(P[i][2], mx_pre[i - 1] if i > 0 else MIN)
			mx_suf[lP - 1 - i] = max(P[lP - 1 - i][3], mx_suf[lP - i] if i > 0 else MIN)
	(m, M) = (min(A[0]), max(A[0]))
	Q.append((m, 0, -m, m))
	if len(A[0]) > 0:
		Q.append((M, 0, -M, M))
	for n in range(1, N):
		a = A[n]
		Q.sort()
		(P, Q) = (Q, [])
		process_min_max()
		for i in range(len(a)):
			(first, last) = (a[i], a[i - 1])
			ins_pos = bisect.bisect_left(P, (first, 0, 0, 0))
			pos_pre = ins_pos - 1
			pos_suf = ins_pos
			if pos_pre < 0:
				cost1 = MIN
			else:
				cost1 = mx_pre[pos_pre] + first * n
			if pos_suf > len(P) - 1:
				cost2 = MIN
			else:
				cost2 = mx_suf[pos_suf] - first * n
			cost = max(cost1, cost2)
			Q.append((last, cost, -last * (n + 1) + cost, last * (n + 1) + cost))
	return max(map(lambda x: x[1], Q))
T = int(input())
for _ in range(T):
	(N, A) = read_test()
	sol = solve_test(N, A)
	print(sol)


t = int(input())
for i in range(t):
	n = int(input())
	lengths = []
	arr = []
	final_arr = []
	for k in range(n):
		temp_array = [int(j) for j in input().split()]
		arr.append(temp_array[1:])
		lengths.append(temp_array[0])
		final_arr.append([0] * lengths[k])
	if n == 1:
		print(0)
	else:
		final_arr[0] = arr[0]
		(m1, m2) = (max(arr[0]), min(arr[0]))
		for j in range(lengths[1]):
			final_arr[1][j] = max(abs(arr[1][j] - m1), abs(arr[1][j] - m2))
		for s in range(2, n):
			max1 = -100000000000.0
			max2 = -100000000000.0
			for f in range(lengths[s - 1]):
				foo = final_arr[s - 1][(f + 1) % lengths[s - 1]] + s * arr[s - 1][f]
				bar = final_arr[s - 1][(f + 1) % lengths[s - 1]] - s * arr[s - 1][f]
				if foo > max1:
					max1 = foo
				if bar > max2:
					max2 = bar
			for g in range(lengths[s]):
				final_arr[s][g] = max(max1 - s * arr[s][g], max2 + s * arr[s][g])
		print(max(final_arr[-1]))


for _ in range(int(input())):
	N = int(input())
	Ingr = []
	IngrSize = []
	Total = 0
	maxLen = 0
	for i in range(N):
		Ingr.append(list(map(int, input().split())))
		IngrSize.append(Ingr[-1][0])
		if maxLen < Ingr[-1][0]:
			maxLen = Ingr[-1][0]
		Ingr[-1].pop(0)
	if N <= 1:
		print(0)
		continue
	DPArr = []
	for i in range(IngrSize[0]):
		DPArr.append(tuple([Ingr[0][i], 0]))
	for i in range(1, N):
		newDPArr = [[0, 0] for a in range(IngrSize[i])]
		DPArr.sort()
		LeftMax = []
		RightMax = []
		LM = DPArr[0][1] - DPArr[0][0]
		RM = DPArr[-1][1] + DPArr[-1][0]
		LeftMax.append(LM)
		RightMax.append(RM)
		for j in range(1, IngrSize[i - 1]):
			if LM < DPArr[j][1] - DPArr[j][0]:
				LM = DPArr[j][1] - DPArr[j][0]
			if RM < DPArr[IngrSize[i - 1] - 1 - j][1] + DPArr[IngrSize[i - 1] - 1 - j][0]:
				RM = DPArr[IngrSize[i - 1] - 1 - j][1] + DPArr[IngrSize[i - 1] - 1 - j][0]
			LeftMax.append(LM)
			RightMax.append(RM)
		RightMax.reverse()
		for j in range(IngrSize[i]):
			Max = 0
			VALUE = Ingr[i][j] * i
			if VALUE <= DPArr[0][0]:
				Max = RightMax[0] - VALUE
			elif VALUE >= DPArr[-1][0]:
				Max = LeftMax[-1] + VALUE
			else:
				M1 = 0
				M2 = 0
				Beg = 0
				End = IngrSize[i - 1] - 1
				while Beg <= End:
					Mid = (Beg + End) // 2
					if VALUE >= DPArr[Mid][0] and DPArr[Mid + 1][0] >= VALUE:
						M1 = LeftMax[Mid] + VALUE
						M2 = RightMax[Mid + 1] - VALUE
						Max = max(M1, M2)
						break
					elif VALUE >= DPArr[Mid][0] and VALUE >= DPArr[Mid + 1][0]:
						Beg = Mid + 1
					else:
						End = Mid - 1
			newDPArr[(j - 1 + IngrSize[i]) % IngrSize[i]][0] = Ingr[i][(j - 1 + IngrSize[i]) % IngrSize[i]] * (i + 1)
			newDPArr[(j - 1 + IngrSize[i]) % IngrSize[i]][1] = Max
		DPArr = newDPArr[:]
	ANS = 0
	for (i, w) in DPArr:
		if w > ANS:
			ANS = w
	print(ANS)


def getPairs(x, k, k1):
	n = len(x)
	y = [(x[i], x[(i + 1) % n]) for i in range(n)]
	ret = []
	for a in [-1, 1]:
		yy = [(z[0] * k1 + z[1] * k * a, z) for z in y]
		yy = sorted(yy)
		mn = yy[0][0]
		mx = yy[-1][0]
		ret += [yy[0][1], yy[-1][1]]
	return ret

def solve(z):
	prev = [0]
	y = []
	n = len(z)
	for (i, x) in enumerate(z):
		if i == 0:
			y = getPairs(x, 0, 1)
			prev = [0] * len(y)
			continue
		n = len(y)
		x = getPairs(x, i, (i + 1) % len(z))
		ret = [0] * len(x)
		for (a, aa) in enumerate(x):
			mx = 0
			for (b, bb) in enumerate(y):
				val = prev[b % n] + i * abs(aa[1] - bb[0])
				if val > mx:
					mx = val
			ret[a] = mx
		prev = ret
		y = x
	return max(prev)
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	x = int(f.readline())
	y = []
	for i in range(x):
		y += [list(map(int, f.readline().split()))[1:]]
	sol = solve(y)
	print(sol)