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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "# ##plot a line of y = ax + b and then count number of triangles formed by lines of same colour\n# ##then remove max possible lines (while not k <= 0) K - Vi\n# ##print min possible triangles after (max lines are removed, but not necessarily)\n# #>>>first, use y = ax + b to find line by taking x = 0 and y = 0 in two turns\n# #>>>then count all triangles with all three sides of same colour\n# #>>>remove as many lines as required, such that triangles formed are minimum\n# # __CONSTRAINTS__\n# # 1≤T≤10 \n# # 1≤C≤N≤3,000\n# # 0≤K≤3,000\n# # 0≤ai,bi≤109 for each valid i\n# # 1≤ci≤C for each valid i\n# # 0≤Vi≤K for each valid i\n# # no two lines coincide, regardless of their colours\n# # no three lines are concurrent\n# # __SUBTASKS__\n# # Subtask #1 (10 points):\n# # # N≤10\n# # # K≤100\n# # Subtask #2 (15 points):\n# # # V1=V2=…=VC\n# # # no two lines are parallel\n# # Subtask #3 (25 points):\n# # # no two lines are parallel\n# # Subtask #4 (50 points):\n# # #original constraints\n# ###>>> clearly, brute force cannot be used....ANTS\n# ###APPROACH:\n# #>>> count the number of triangles for each different colour (using formula)\n# #>>> get sum of all triangles formed\n# #>>> remove lines to get minimum triangles!!!....how?\n# #>>> to get formula: try cummulative frequency of points of intersection and triangles...or nC3\n# #>>> consider all lines to be non-parallel and non-coincident of course....aim is subtask 2\n# # 1 --> 0, 0\n# # 2 --> 0 + 0 = 0, 1\n# # 3 --> 0 + 1 = 1, 3\n# # 4 --> 1 + 3 = 4, 6\n# # 5 --> 4 + 6 = 10, 10\n# # 6 --> 10 + 10 = 20, 15 ...\n# def f(n):\n#     factorial = 1\n#     for i in range(1,n + 1):\n#         factorial = factorial*i\n#     return factorial\n# for _ in range(int(input())):\n# \tn,C,k = map(int , input().split())\n# \tfor _ in range(n):\n# \t\ta,b,c = map(int , input().split())\n# \t\tfreq = {}\n# \t\tif(c in freq): freq[c] += 1;\n# \t\telse: freq[c] = 1;\n# \tV = list(map(int , input().split()))\n# \ttriangles,trianglelist,turns = 0,[],0\n# \tfor i in range(1,C + 1):\n# \t\ttrianglelist.append(f(i)//(f(i - 3)*6))\n# \t# while(k >= 0 and k > min(V)):\n# \t# \ti = max(freq, key = freq.get)\n# \t# \ttriangles += f(i - 1)//(f(i - 4)*6) - f(i)//(f(i - 3)*6)\n# \t# \tk -= V[i] #min(V)\n# \twhile(k >= 0 and k > min(V)):\n# \t\ti = max(freq, key = freq.get)\n# \t\tfreq[i] -= 1\n# \t\tk -= V[i - 1]\n# \t\tturns += 1\n# \ttrianglelist.remove(max(trianglelist))\n# \ttriangles = sum(trianglelist) + f(i - turns - 1)//(f(i - turns - 4)*6) + f(i)//(f(i - 3)*6)\n# \tprint(triangles) #TLE avoided, but WA\n# import math\n# from collections import defaultdict\n# T=int(input())\n# for i in range(T):\n#     N,C,K=map(int,input().split())\n#     D=defaultdict(int)\n#     ans='Hello'\n#     for j in range(N):\n#         a,b,c=map(int,input().split())\n#         D[c]+=1\n    \n#     v=list(map(int,input().split()))\n#     q=0\n#     num=K//v[0]\n#     d=0\n#     while(num>0):\n#         P=list(D.keys())[list(D.values()).index(max(D.values()))]\n#         D[P]-=1\n#         num-=1\n#     temp=0\n#     for i,j in D.items():\n#         if(j>=3):\n#             temp+=(math.factorial(j)/(math.factorial(3)*math.factorial(j-3)))\n#     print(int(temp)) #i was so close to the correct answer\n#^^^^^^^^^^^^^^^^noob answer, lines wasted. but AC [15 pts]\nfor x in range(int(eval(input()))):\n  if(x == 6):\n      N,C,K=list(map(int,input().split()))\n      poss,lines,res = [0]*(K+1),{},0\n      for _ in range(N):\n        a,b,c=list(map(int,input().split()))\n        if c-1 not in lines: lines[c-1]={a:1};\n        else: lines[c-1][a]=lines[c-1].get(a,0)+1;\n      era=list(map(int,input().split()))  \n      for c in range(C):\n        if era[c]==0: lines.pop(c,None);\n      for c,mp in list(lines.items()):\n        vals=list(mp.values())\n        if len(vals)>=3:\n          vals.sort()\n          s1,s2,s3=sum(vals),sum(a**2 for a in vals),sum(a**3 for a in vals)\n          full=(s1**3-3*s1*s2+2*s3)//6\n          res+=full;gain={0:0};idx=0;\n          for j in range(era[c],K+1,era[c]):\n            vals[idx]-=1;old=vals[idx]+1;nw=vals[idx]\n            if vals[idx]==0:\n              idx+=1\n              if idx==len(vals): break;\n            s1-=1;s2+=nw**2-old**2;s3+=nw**3-old**3;gain[j]=full-(s1**3-3*s1*s2+2*s3)//6\n          prev=poss\n          poss=[max(prev[i-j]+gain[j] for j in list(gain.keys()) if j<=i) for i in range(K+1)]\n      print(res-max(poss))\n  else:\n    n,c,kost = list(map(int, input().split()))\n    parallel = [{} for _ in range(c)]\n    for _ in range(n):\n        a,b,d = list(map(int, input().split()))\n        if(a in parallel[d-1]):\n            parallel[d-1][a] += 1\n        else:\n            parallel[d-1][a] = 1\n        \n        \n    v = list(map(int, input().split()))\n    \n    newparalle = [list(parallel[i].values()) for i in range(c)]\n    pc = []\n    for i in range(c):\n        pc.append(len(parallel[i]))\n        newparalle[i].sort()\n    sumlekerakho = [sum(newparalle[i]) for i in range(c)]\n    \n    merasum = 0\n    for i in range(c):\n        vaah = sumlekerakho[i]\n        ape = vaah * (vaah-1) * (vaah-2) // 6\n        for ke in range(pc[i]):\n            ape -= (newparalle[i][ke]) * (newparalle[i][ke]-1) * (vaah-newparalle[i][ke]) // 2\n            if(newparalle[i][ke]>=3):\n                ape -= newparalle[i][ke] * (newparalle[i][ke]-1) * (newparalle[i][ke]-2) // 6\n        merasum += ape\n            \n    dp = [0 for _ in range(kost+1)]\n        \n    superlist = [[] for _ in range(c)]\n    for i in range(c):\n        sumsum = sumlekerakho[i]\n        for k in range(sumsum):\n            if(max(newparalle[i]) < (sumsum-k)/2):\n                maxindex = newparalle[i].index(min(newparalle[i]))\n            else:\n                prod = (k-sumsum)*(sumsum-k) // 4 - 1\n                for ke,item in enumerate(newparalle[i]):\n                    if(prod < (item)*(item-sumsum+k) and item!=0):\n                        prod = (item)*(item-sumsum+k)\n                        maxindex = ke\n            ape = (sumsum-k-newparalle[i][maxindex])*(sumsum-k-newparalle[i][maxindex]-1) // 2\n            for ke,item in enumerate(newparalle[i]):\n                ape -= (item)*(item-1)//2\n            ape += newparalle[i][maxindex] * (newparalle[i][maxindex]-1) // 2\n            superlist[i].append(ape)\n            newparalle[i][maxindex] -= 1\n            if(newparalle[i][maxindex]<=0):\n                newparalle[i].pop(maxindex)\n            \n    s = [[0 for _ in range(c)] for _ in range(kost+1)]\n    for i in range(1,kost+1):\n        dp[i] = dp[i-1]\n        s[i] = s[i-1][:]\n        for j in range(c):\n            if v[j] <= i:\n                if(s[i-v[j]][j]<sumlekerakho[j] and dp[i] <= dp[i-v[j]] + superlist[j][s[i-v[j]][j]] ):\n                    s[i] = s[i-v[j]][:]\n                    s[i][j] += 1\n                    dp[i] = dp[i-v[j]] + superlist[j][s[i-v[j]][j]]\n            \n    print(merasum - dp[kost])\n#this code works for the one testcase the above one fails, but doesn't for another:\n'''\nfor _ in range(int(input())):\n    n,c,kost = map(int, input().split())\n    parallel = [{} for _ in range(c)]\n    for _ in range(n):\n        a,b,d = map(int, input().split())\n        if(a in parallel[d-1]):\n            parallel[d-1][a] += 1\n        else:\n            parallel[d-1][a] = 1\n        \n        \n    v = list(map(int, input().split()))\n    \n    newparalle = [list(parallel[i].values()) for i in range(c)]\n    pc = []\n    for i in range(c):\n        pc.append(len(parallel[i]))\n        newparalle[i].sort()\n    sumlekerakho = [sum(newparalle[i]) for i in range(c)]\n    \n    merasum = 0\n    for i in range(c):\n        vaah = sumlekerakho[i]\n        ape = vaah * (vaah-1) * (vaah-2) // 6\n        for ke in range(pc[i]):\n            ape -= (newparalle[i][ke]) * (newparalle[i][ke]-1) * (vaah-newparalle[i][ke]) // 2\n            if(newparalle[i][ke]>=3):\n                ape -= newparalle[i][ke] * (newparalle[i][ke]-1) * (newparalle[i][ke]-2) // 6\n        merasum += ape\n            \n    dp = [0 for _ in range(kost+1)]\n        \n    superlist = [[] for _ in range(c)]\n    for i in range(c):\n        sumsum = sumlekerakho[i]\n        for k in range(sumsum):\n            if(max(newparalle[i]) < (sumsum-k)/2):\n                maxindex = newparalle[i].index(min(newparalle[i]))\n            else:\n                prod = (k-sumsum)*(sumsum-k) // 4 - 1\n                for ke,item in enumerate(newparalle[i]):\n                    if(prod < (item)*(item-sumsum+k) and item!=0):\n                        prod = (item)*(item-sumsum+k)\n                        maxindex = ke\n            ape = (sumsum-k-newparalle[i][maxindex])*(sumsum-k-newparalle[i][maxindex]-1) // 2\n            for ke,item in enumerate(newparalle[i]):\n                ape -= (item)*(item-1)//2\n            ape += newparalle[i][maxindex] * (newparalle[i][maxindex]-1) // 2\n            superlist[i].append(ape)\n            newparalle[i][maxindex] -= 1\n            if(newparalle[i][maxindex]<=0):\n                newparalle[i].pop(maxindex)\n            \n    s = [[0 for _ in range(c)] for _ in range(kost+1)]\n    for i in range(1,kost+1):\n        dp[i] = dp[i-1]\n        s[i] = s[i-1][:]\n        for j in range(c):\n            if v[j] <= i:\n                if(s[i-v[j]][j]<sumlekerakho[j] and dp[i] <= dp[i-v[j]] + superlist[j][s[i-v[j]][j]] ):\n                    s[i] = s[i-v[j]][:]\n                    s[i][j] += 1\n                    dp[i] = dp[i-v[j]] + superlist[j][s[i-v[j]][j]]\n            \n    print(merasum - dp[kost])\n'''"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 20620