Given $K$ arrays of length $N$ where the elements are bounded in the range $[L, R]$.

The Function value of an array is defined as the sum of all elements present in it.

In one move you can change at most $1$ element from all the arrays and the changed value must lie within the range $[L, R]$. 

What is the minimum number of operations required to make the function value of all arrays equal?

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains four space-separated integers $K$, $N$, $L$, $R$.
Next $K$ lines contains an array of length $N$.

------  Output  ------
For each test case, print the minimum number of operations needed to make the function value of all arrays equal in a new line.

------  Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ K ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ N*K ≤ 10^{5}$
$1 ≤ L ≤ R ≤ 10^{9}$

------  Example Input ------

1
4 3 1 9
1 1 2
1 2 3
1 2 4
1 2 2

------  Example Output ------

1

------  Explanation  ------
Change array $1$ to $[1, 3, 2]$
No change in array $2$ 
Change array $3$ to $[1, 2, 3]$
Change array $4$ to $[1, 2, 3]$
Sum of all arrays is equal.

Source: codechef | Difficulty: VERY_HARD
Tags: Greedy algorithms

Sorting

Complete search


Solutions:
t = int(input())
for i in range(t):
	(k, n, l, r) = map(int, input().split())
	a = [sorted(map(int, input().split())) for j in range(k)]
	x = [[sum(a[i])] * 2 for i in range(k)]
	for j in range(n + 1):
		if min((x[z][1] for z in range(k))) >= max((x[z][0] for z in range(k))):
			print(j)
			break
		for y in range(k):
			x[y][1] += r - a[y][j]
			x[y][0] -= a[y][-1 - j] - l


for _ in range(int(input())):
	(k, N, l, r) = map(int, input().split())
	A = [sorted(map(int, input().split())) for j in range(k)]
	X = [[sum(A[i])] * 2 for i in range(k)]
	for i in range(N + 1):
		if min((X[j][1] for j in range(k))) >= max((X[j][0] for j in range(k))):
			print(i)
			break
		for j in range(k):
			X[j][1] += r - A[j][i]
			X[j][0] -= A[j][-1 - i] - l


for t in range(int(input())):
	(k, n, L, R) = map(int, input().split())
	A = [sorted(map(int, input().split())) for i in range(k)]
	X = [[sum(A[i])] * 2 for i in range(k)]
	for i in range(n + 1):
		if min([X[i][1] for i in range(k)]) >= max([X[i][0] for i in range(k)]):
			print(i)
			break
		for j in range(k):
			X[j][0] -= A[j][-i - 1] - L
			X[j][1] += R - A[j][i]


for i in range(int(input())):
	(K, N, L, R) = map(int, input().split())
	A = [sorted(map(int, input().split())) for i in range(K)]
	X = [[sum(A[i])] * 2 for i in range(K)]
	for i in range(N + 1):
		if min((X[i][1] for i in range(K))) >= max((X[i][0] for i in range(K))):
			print(i)
			break
		for j in range(K):
			X[j][0] -= A[j][-i - 1] - L
			X[j][1] += R - A[j][i]


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
tc = 1
tc = int(input())
for test in range(1, tc + 1):
	(k, n, l, r) = inp()
	a = []
	Max = [0] * k
	Min = [0] * k
	for i in range(k):
		a.append(sorted(inp()))
		Max[i] = Min[i] = sum(a[-1])
	for i in range(n + 1):
		Mn = -INF
		Mx = INF
		left = i - 1
		right = n - i
		for j in range(k):
			if left >= 0:
				Min[j] = Min[j] - a[j][right] + l
				Max[j] = Max[j] - a[j][left] + r
			Mn = max(Min[j], Mn)
			Mx = min(Max[j], Mx)
		if Mn <= Mx:
			print(i)
			break


def i():
	return int(input())

def s():
	return input()

def l():
	return list(map(int, input().split()))

def m():
	return map(int, input().split())
for _ in range(i()):
	(k, N, l, r) = map(int, input().split())
	A = [sorted(map(int, input().split())) for j in range(k)]
	X = [[sum(A[i])] * 2 for i in range(k)]
	for i in range(N + 1):
		if min((X[j][1] for j in range(k))) >= max((X[j][0] for j in range(k))):
			print(i)
			break
		for j in range(k):
			X[j][1] += r - A[j][i]
			X[j][0] -= A[j][-1 - i] - l