After failing to clear his school mathematics examination, infinitepro decided to prepare very hard for his upcoming re-exam, starting with the topic he is weakest at ― computational geometry.
Being an artist, infinitepro has C$C$ pencils (numbered 1$1$ through C$C$); each of them draws with one of C$C$ distinct colours. He draws N$N$ lines (numbered 1$1$ through N$N$) in a 2D Cartesian coordinate system; for each valid i$i$, the i$i$-th line is drawn with the ci$c_i$-th pencil and it is described by the equation y=ai⋅x+bi$y = a_i \cdot x + b_i$.
Now, infinitepro calls a triangle truly-geometric if each of its sides is part of some line he drew and all three sides have the same colour. He wants to count these triangles, but there are too many of them! After a lot of consideration, he decided to erase a subset of the N$N$ lines he drew. He wants to do it with his eraser, which has length K$K$.
Whenever erasing a line with a colour i$i$, the length of the eraser decreases by Vi$V_i$. In other words, when the eraser has length k$k$ and we use it to erase a line with a colour i$i$, the length of the eraser decreases to k−Vi$k-V_i$; if k<Vi$k < V_i$, it is impossible to erase such a line.
Since infinitepro has to study for the re-exam, he wants to minimise the number of truly-geometric triangles. Can you help him find the minimum possible number of truly-geometric triangles which can be obtained by erasing a subset of the N$N$ lines in an optimal way? He promised a grand treat for you if he passes the examination!

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of the input contains three space-separated integers N$N$, C$C$ and K$K$.
- N$N$ lines follow. For each i$i$ (1≤i≤N$1 \le i \le N$), the i$i$-th of these lines contains three space-separated integers ai$a_i$, bi$b_i$ and ci$c_i$.
- The last line contains C$C$ space-separated integers V1,V2,…,VC$V_1, V_2, \ldots, V_C$.

-----Output-----
For each test case, print a single line containing one integer ― the smallest possible number of truly-geometric triangles after erasing lines.

-----Constraints-----
- 1≤T≤10$1 \le T \le 10$
- 1≤C≤N≤3,000$1 \le C \le N \le 3,000$
- 0≤K≤3,000$0 \le K \le 3,000$
- 0≤ai,bi≤109$0 \le a_i, b_i \le 10^9$ for each valid i$i$
- 1≤ci≤C$1 \le c_i \le C$ for each valid i$i$
- 0≤Vi≤K$0 \le V_i \le K$ for each valid i$i$
- no two lines coincide, regardless of their colours
- no three lines are concurrent

-----Subtasks-----
Subtask #1 (10 points):
- N≤10$N \le 10$
- K≤100$K \le 100$
Subtask 2 (15 points):
- V1=V2=…=VC$V_1 = V_2 = \ldots = V_C$
- no two lines are parallel
Subtask #3 (25 points): no two lines are parallel
Subtask #4 (50 points): original constraints

-----Example Input-----
2
7 2 13
1 10 1
1 14 2
6 4 1
2 2 1
0 12 2
2 11 2
0 6 1
8 10
6 1 20
1 5 1
2 11 1
4 0 1
6 8 1
0 11 1
3 3 1
9

-----Example Output-----
2
4

-----Explanation-----
Example case 1: We can remove exactly one line. Initially, we have 5$5$ truly geometric triangles (see the image below; red is colour 1$1$ and green is colour 2$2$).
- Removing any line with colour 2$2$ brings the total number of truly-geometric triangles down to 4+0=4$4+0=4$.
- Removing any line with colour 1$1$ brings the total number of truly-geometric triangles down to 1+1=2$1+1=2$.
Thus, the smallest number of truly-geometric triangles we can obtain is 2$2$.

Example case 2: We can remove at most 2$2$ lines and removing any 2$2$ lines gives us a total of 4$4$ truly-geometric triangles.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from collections import Counter
from math import factorial

def nc3(n):
	a = factorial(n)
	b = factorial(n - 3)
	return a / (b * 6)

def rem(s, k):
	t = -1
	x = -1
	for i in range(len(s)):
		if s[i][0] > 2 and s[i][1] <= k:
			if s[i][0] > 3:
				ch = (nc3(s[i][0]) - nc3(s[i][0] - 1)) / s[i][1]
			else:
				ch = 1 / s[i][1]
			if t < ch:
				t = ch
				x = i
	return x
t = int(input())
for x in range(t):
	(n, c, k) = map(int, input().split())
	l = {}
	for i in range(n):
		(a, b, e) = map(int, input().split())
		if e in l:
			l[e].append(a)
		else:
			l[e] = []
			l[e].append(a)
	v = list(map(int, input().split()))
	s = []
	for i in range(1, c + 1):
		if i in l:
			s += [[len(l[i]), v[i - 1]]]
	s.sort(key=lambda x: x[0], reverse=True)
	while True:
		ma = rem(s, k)
		if ma <= -1:
			break
		else:
			s[ma][0] -= 1
			k = k - s[ma][1]
	re = 0
	for i in s:
		if i[0] > 2:
			re = re + nc3(i[0])
	print(int(re))


t = int(input())
for t1 in range(t):
	(n, c, k1) = (int(i) for i in input().split())
	lis = [dict([]) for i in range(c + 1)]
	ma = 1
	for i in range(n):
		x = [int(j) for j in input().split()]
		if x[0] in lis[x[2]]:
			lis[x[2]][x[0]] += 1
		else:
			lis[x[2]][x[0]] = 1
		ma = max(ma, lis[x[2]][x[0]])
	de = [int(i) for i in input().split()]
	if ma == 1:
		kna = [[0 for i in range(k1 + 1)], [0 for i in range(k1 + 1)]]
		ct = 0
		tot = 0
		for i in range(1, c + 1):
			k = len(lis[i])
			v = de[i - 1]
			tot += k * (k - 1) * (k - 2) / 6
			for j in range(1, len(lis[i]) - 1):
				be = ct % 2
				no = (be + 1) % 2
				val = (k - j) * (k - j - 1) / 2
				for z in range(k1 + 1):
					if z >= v:
						kna[no][z] = max(kna[be][z], kna[be][z - v] + val)
					else:
						kna[no][z] = kna[be][z]
				ct += 1
		tot = tot - max(kna[0][k1], kna[1][k1])
		print(int(tot))
	else:
		kna = [[0 for i in range(k1 + 1)], [0 for i in range(k1 + 1)]]
		ct = 0
		tot = 0
		for i in range(1, c + 1):
			nlist = [lis[i][j] for j in lis[i]]
			nlist.sort()
			k = len(nlist)
			v = de[i - 1]
			su = 0
			tri = 0
			for j in range(k - 3, -1, -1):
				su += nlist[j + 2]
				tri += su * nlist[j + 1]
				tot += tri * nlist[j]
				val = tri
				for z1 in range(nlist[j]):
					be = ct % 2
					no = (be + 1) % 2
					for z in range(k1 + 1):
						if z >= v:
							kna[no][z] = max(kna[be][z], kna[be][z - v] + val)
						else:
							kna[no][z] = kna[be][z]
					ct += 1
		tot = tot - max(kna[0][k1], kna[1][k1])
		print(int(tot))


import copy

def calprofit(lines_removed, j):
	lines_set = copy.deepcopy(differentline[j])
	iterator = 0
	while iterator < len(lines_set) and lines_removed > 0:
		possible = min(lines_set[iterator], lines_removed)
		lines_set[iterator] = lines_set[iterator] - possible
		lines_removed = lines_removed - possible
		iterator = iterator + 1
	if lines_removed > 0:
		return 0
	sum1 = 0
	for iterator1 in range(len(lines_set)):
		sum1 = sum1 + lines_set[iterator1]
	sum2 = 0
	temp = [0] * (len(lines_set) + 1)
	for iterator2 in range(len(lines_set)):
		temp[iterator2] = lines_set[iterator2] * (sum1 - lines_set[iterator2])
		sum2 = sum2 + temp[iterator2]
	sum2 = sum2 // 2
	sum3 = 0
	for iterator3 in range(len(lines_set)):
		sum3 = sum3 + lines_set[iterator3] * (sum2 - temp[iterator3])
	sum3 = sum3 // 3
	return sum3
for i in range(int(input())):
	(n, c, k) = [int(i) for i in input().split()]
	color = []
	for i in range(c + 1):
		color.append(dict())
	for i in range(n):
		(a, b, co) = [int(i) for i in input().split()]
		if color[co].get(a, 0):
			color[co][a] = color[co][a] + 1
		else:
			color[co][a] = 1
	differentline = []
	for i in color:
		chk = list(i.values())
		chk.sort()
		differentline.append(chk)
	weight = [0] + [int(i) for i in input().split()]
	profit = []
	dp = []
	for i in range(k + 1):
		profitdemo = []
		dpdemo = []
		for j in range(c + 1):
			profitdemo.append(-1)
			if j == 0:
				dpdemo.append(0)
			else:
				dpdemo.append(10 ** 20 + 7)
		profit.append(profitdemo)
		dp.append(dpdemo)
	for i in range(k + 1):
		for j in range(1, c + 1):
			removable_item = i // weight[j]
			for lines_removed in range(removable_item + 1):
				demo = lines_removed * weight[j]
				if profit[lines_removed][j] == -1:
					profit[lines_removed][j] = calprofit(lines_removed, j)
				dp[i][j] = min(dp[i][j], dp[i - demo][j - 1] + profit[lines_removed][j])
	print(dp[k][c])


import collections
from itertools import combinations

def checkintersection(e1, e2, e3):
	if e1[0] - e2[0] != 0:
		x1 = (e1[1] - e2[1]) / (e1[0] - e2[0])
		y1 = e1[0] * x1 + e1[1]
	else:
		return True
	if e2[0] - e3[0] != 0:
		x2 = (e2[1] - e3[1]) / (e2[0] - e3[0])
		y2 = e2[0] * x2 + e2[1]
	else:
		return True
	return x1 == x2 and y1 == y2

def checkparallel(m1, m2, m3):
	return m1 == m2 or m2 == m3 or m1 == m3
for _ in range(int(input())):
	(N, C, K) = map(int, input().split())
	A = []
	D = {}
	EQ = {}
	for i in range(N):
		(a, b, c) = map(int, input().split())
		if c not in D:
			D[c] = []
		D[c].append((a, b, c))
		EQ[a, b, c] = 0
	V = list(map(int, input().split()))
	V.insert(0, 0)
	nextflag = 1
	while K >= 0 and nextflag == 1:
		nextflag = 0
		ans = 0
		for col in D:
			if len(D[col]) >= 3:
				triangles = list(combinations(D[col], 3))
				triangles = list(set(triangles))
				for tri in triangles:
					boolp = checkparallel(tri[0][0], tri[1][0], tri[2][0])
					booli = checkintersection(tri[0], tri[1], tri[2])
					if boolp == False and booli == False:
						EQ[tri[0]] += 1
						EQ[tri[1]] += 1
						EQ[tri[2]] += 1
						ans += 1
		EQ = {k: v for (k, v) in sorted(EQ.items(), key=lambda item: item[1], reverse=True)}
		for i in EQ:
			e = i
			if V[e[2]] <= K:
				K -= V[e[2]]
				nextflag = 1
				D[e[2]].remove(e)
				del EQ[i]
				break
	print(ans)


for x in range(int(eval(input()))):
	if x == 6:
		(N, C, K) = list(map(int, input().split()))
		(poss, lines, res) = ([0] * (K + 1), {}, 0)
		for _ in range(N):
			(a, b, c) = list(map(int, input().split()))
			if c - 1 not in lines:
				lines[c - 1] = {a: 1}
			else:
				lines[c - 1][a] = lines[c - 1].get(a, 0) + 1
		era = list(map(int, input().split()))
		for c in range(C):
			if era[c] == 0:
				lines.pop(c, None)
		for (c, mp) in list(lines.items()):
			vals = list(mp.values())
			if len(vals) >= 3:
				vals.sort()
				(s1, s2, s3) = (sum(vals), sum((a ** 2 for a in vals)), sum((a ** 3 for a in vals)))
				full = (s1 ** 3 - 3 * s1 * s2 + 2 * s3) // 6
				res += full
				gain = {0: 0}
				idx = 0
				for j in range(era[c], K + 1, era[c]):
					vals[idx] -= 1
					old = vals[idx] + 1
					nw = vals[idx]
					if vals[idx] == 0:
						idx += 1
						if idx == len(vals):
							break
					s1 -= 1
					s2 += nw ** 2 - old ** 2
					s3 += nw ** 3 - old ** 3
					gain[j] = full - (s1 ** 3 - 3 * s1 * s2 + 2 * s3) // 6
				prev = poss
				poss = [max((prev[i - j] + gain[j] for j in list(gain.keys()) if j <= i)) for i in range(K + 1)]
		print(res - max(poss))
	else:
		(n, c, kost) = list(map(int, input().split()))
		parallel = [{} for _ in range(c)]
		for _ in range(n):
			(a, b, d) = list(map(int, input().split()))
			if a in parallel[d - 1]:
				parallel[d - 1][a] += 1
			else:
				parallel[d - 1][a] = 1
		v = list(map(int, input().split()))
		newparalle = [list(parallel[i].values()) for i in range(c)]
		pc = []
		for i in range(c):
			pc.append(len(parallel[i]))
			newparalle[i].sort()
		sumlekerakho = [sum(newparalle[i]) for i in range(c)]
		merasum = 0
		for i in range(c):
			vaah = sumlekerakho[i]
			ape = vaah * (vaah - 1) * (vaah - 2) // 6
			for ke in range(pc[i]):
				ape -= newparalle[i][ke] * (newparalle[i][ke] - 1) * (vaah - newparalle[i][ke]) // 2
				if newparalle[i][ke] >= 3:
					ape -= newparalle[i][ke] * (newparalle[i][ke] - 1) * (newparalle[i][ke] - 2) // 6
			merasum += ape
		dp = [0 for _ in range(kost + 1)]
		superlist = [[] for _ in range(c)]
		for i in range(c):
			sumsum = sumlekerakho[i]
			for k in range(sumsum):
				if max(newparalle[i]) < (sumsum - k) / 2:
					maxindex = newparalle[i].index(min(newparalle[i]))
				else:
					prod = (k - sumsum) * (sumsum - k) // 4 - 1
					for (ke, item) in enumerate(newparalle[i]):
						if prod < item * (item - sumsum + k) and item != 0:
							prod = item * (item - sumsum + k)
							maxindex = ke
				ape = (sumsum - k - newparalle[i][maxindex]) * (sumsum - k - newparalle[i][maxindex] - 1) // 2
				for (ke, item) in enumerate(newparalle[i]):
					ape -= item * (item - 1) // 2
				ape += newparalle[i][maxindex] * (newparalle[i][maxindex] - 1) // 2
				superlist[i].append(ape)
				newparalle[i][maxindex] -= 1
				if newparalle[i][maxindex] <= 0:
					newparalle[i].pop(maxindex)
		s = [[0 for _ in range(c)] for _ in range(kost + 1)]
		for i in range(1, kost + 1):
			dp[i] = dp[i - 1]
			s[i] = s[i - 1][:]
			for j in range(c):
				if v[j] <= i:
					if s[i - v[j]][j] < sumlekerakho[j] and dp[i] <= dp[i - v[j]] + superlist[j][s[i - v[j]][j]]:
						s[i] = s[i - v[j]][:]
						s[i][j] += 1
						dp[i] = dp[i - v[j]] + superlist[j][s[i - v[j]][j]]
		print(merasum - dp[kost])


from sys import stdin, setrecursionlimit, stdout
from collections import deque, defaultdict, Counter
from math import log2, log, ceil, sqrt
from operator import *
input = stdin.readline
setrecursionlimit(int(200000.0))

def getstr():
	return input()[:-1]

def getint():
	return int(input())

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

def getint1():
	return list(map(lambda x: int(x) - 1, input().split()))
jn = lambda x, l: x.join(map(str, l))

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return res

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def maxSlidingWindow(nums, k):
	(windowSum, maxSum) = (0, 0)
	windowSum = sum(nums[:k])
	for end in range(k, len(nums)):
		windowSum += nums[end] - nums[end - k]
		maxSum = max(maxSum, windowSum)
	return maxSum

def twoSum(nums, target):
	left = 0
	right = len(nums) - 1
	while left <= right:
		if nums[left] + nums[right] == target:
			return [left, right]
		elif nums[left] + nums[right] < target:
			left += 1
		else:
			right -= 1
	return

def prefix(arr):
	a = map(add, arr.insert(0, 0))
	return a

def primefs(n):
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def binsearch(a, l, r, x):
	while l <= r:
		mid = l + (r - 1) // 2
		if a[mid]:
			return mid
		elif a[mid] > x:
			l = mid - 1
		else:
			r = mid + 1
	return -1
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d:
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d:
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = defaultdict(list)
	for i in range(n):
		(x, y) = mi()
		d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans
MAXN = int(1000000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
(y, n) = ('YES', 'NO')
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}

def solve():
	(n, c, k) = map(int, input().split())
	d = {}
	for i in range(n):
		(a, b, c) = map(int, input().split())
		if c not in d.keys():
			d[c] = 1
		else:
			d[c] += 1
	v = list(map(int, input().split()))
	l_r = k // v[0]
	l = list(d.values())
	i = 0
	while l_r != 0:
		l[l.index(max(l))] -= 1
		l_r -= 1
	count = 0
	for i in l:
		count += i * (i - 1) * (i - 2) // 6
	print(count)

def __starting_point():
	for _ in range(int(input())):
		solve()
__starting_point()


for _ in range(int(eval(input()))):
	(N, C, K) = list(map(int, input().split()))
	(poss, lines, res) = ([0] * (K + 1), {}, 0)
	for _ in range(N):
		(a, b, c) = list(map(int, input().split()))
		if c - 1 not in lines:
			lines[c - 1] = {a: 1}
		else:
			lines[c - 1][a] = lines[c - 1].get(a, 0) + 1
	era = list(map(int, input().split()))
	for c in range(C):
		if era[c] == 0:
			lines.pop(c, None)
	for (c, mp) in list(lines.items()):
		vals = list(mp.values())
		if len(vals) >= 3:
			vals.sort()
			(s1, s2, s3) = (sum(vals), sum((a ** 2 for a in vals)), sum((a ** 3 for a in vals)))
			full = (s1 ** 3 - 3 * s1 * s2 + 2 * s3) // 6
			res += full
			gain = {0: 0}
			idx = 0
			for j in range(era[c], K + 1, era[c]):
				vals[idx] -= 1
				old = vals[idx] + 1
				nw = vals[idx]
				if vals[idx] == 0:
					idx += 1
					if idx == len(vals):
						break
				s1 -= 1
				s2 += nw ** 2 - old ** 2
				s3 += nw ** 3 - old ** 3
				gain[j] = full - (s1 ** 3 - 3 * s1 * s2 + 2 * s3) // 6
			prev = poss
			poss = [max((prev[i - j] + gain[j] for j in list(gain.keys()) if j <= i)) for i in range(K + 1)]
	print(res - max(poss))