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 = 'from sys import stdin, setrecursionlimit,stdout\r\nfrom collections import deque, defaultdict,Counter\r\nfrom math import log2, log, ceil,sqrt\r\nfrom operator import *\r\ninput = stdin.readline\r\nsetrecursionlimit(int(2e5))\r\ndef getstr(): return input()[:-1]\r\ndef getint(): return int(input())\r\ndef getints(): return list(map(int, input().split()))\r\ndef getint1(): return list(map(lambda x : int(x) - 1, input().split()))\r\njn = lambda x,l: x.join(map(str,l))\r\n# swap_array function\r\ndef swaparr(arr, a,b):\r\n    temp = arr[a];\r\n    arr[a] = arr[b];\r\n    arr[b] = temp\r\n \r\n## gcd function\r\ndef gcd(a,b):\r\n    if a == 0:\r\n        return b\r\n    return gcd(b%a, a)\r\n \r\n## nCr function efficient using Binomial Cofficient\r\ndef nCr(n, k): \r\n    if(k > n - k): \r\n        k = n - k \r\n    res = 1\r\n    for i in range(k): \r\n        res = res * (n - i) \r\n        res = res / (i + 1) \r\n    return res \r\n \r\n## upper bound function code -- such that e in a[:i] e < x;\r\ndef upper_bound(a, x, lo=0):\r\n    hi = len(a)\r\n    while lo < hi:\r\n        mid = (lo+hi)//2\r\n        if a[mid] < x:\r\n            lo = mid+1\r\n        else:\r\n            hi = mid\r\n    return lo\r\n \r\n\r\n# sliding window ---\r\n\r\ndef maxSlidingWindow(nums,k):\r\n    windowSum,maxSum = 0,0\r\n    windowSum = sum(nums[:k])\r\n    for end in range(k,len(nums)):\r\n        windowSum += nums[end]-nums[end - k]\r\n        maxSum = max(maxSum,windowSum)\r\n    return maxSum\r\n\r\n\r\n# Two Pointer \r\ndef twoSum(nums, target):\r\n        left = 0\r\n        right = len(nums)-1\r\n        while left <= right:\r\n            if nums[left]+nums[right] == target:\r\n                return [left,right]\r\n            elif nums[left]+nums[right] < target:\r\n                left +=  1\r\n            else:\r\n                right -= 1\r\n        return \r\n\r\n# prefix sum\r\n\r\ndef prefix(arr):\r\n    a = map(add,arr.insert(0,0))\r\n    return a\r\n\r\n# Modular Inverse\r\n# y-1 = y(p-2)%p\r\n\r\n# String Matching\r\n\r\n\r\n\r\n\r\n\r\n## prime factorization\r\ndef primefs(n):\r\n    ## if n == 1    ## calculating primes\r\n    primes = {}\r\n    while(n%2 == 0):\r\n        primes[2] = primes.get(2, 0) + 1\r\n        n = n//2\r\n    for i in range(3, int(n**0.5)+2, 2):\r\n        while(n%i == 0):\r\n            primes[i] = primes.get(i, 0) + 1\r\n            n = n//i\r\n    if n > 2:\r\n        primes[n] = primes.get(n, 0) + 1\r\n    ## prime factoriazation of n is stored in dictionary\r\n    ## primes and can be accesed. O(sqrt n)\r\n    return primes\r\n \r\n## MODULAR EXPONENTIATION FUNCTION\r\ndef power(x, y, p): \r\n    res = 1\r\n    x = x % p  \r\n    if (x == 0) : \r\n        return 0\r\n    while (y > 0) : \r\n        if ((y & 1) == 1) : \r\n            res = (res * x) % p \r\n        y = y >> 1      \r\n        x = (x * x) % p \r\n    return res \r\n \r\n## DISJOINT SET UNINON FUNCTIONS\r\ndef swap(a,b):\r\n    temp = a\r\n    a = b\r\n    b = temp\r\n    return a,b\r\n \r\n# find function with path compression included (recursive)\r\n# def find(x, link):\r\n#     if link[x] == x:\r\n#         return x\r\n#     link[x] = find(link[x], link);\r\n#     return link[x];\r\n \r\n# find function with path compression (ITERATIVE)\r\ndef find(x, link):\r\n    p = x;\r\n    while( p != link[p]):\r\n        p = link[p];\r\n    \r\n    while( x != p):\r\n        nex = link[x];\r\n        link[x] = p;\r\n        x = nex;\r\n    return p;\r\n \r\n \r\n# the union function which makes union(x,y)\r\n# of two nodes x and y\r\ndef union(x, y, link, size):\r\n    x = find(x, link)\r\n    y = find(y, link)\r\n    if size[x] < size[y]:\r\n        x,y = swap(x,y)\r\n    if x != y:\r\n        size[x] += size[y]\r\n        link[y] = x\r\n \r\n## returns an array of boolean if primes or not USING SIEVE OF ERATOSTHANES\r\ndef sieve(n): \r\n    prime = [True for i in range(n+1)] \r\n    p = 2\r\n    while (p * p <= n): \r\n        if (prime[p] == True): \r\n            for i in range(p * p, n+1, p):\r\n                prime[i] = False\r\n        p += 1\r\n    return prime\r\n\r\n\r\n# Binary Search functions\r\ndef binsearch(a, l, r, x):\r\n    while l <= r:\r\n        mid = l + (r-1)//2\r\n        if a[mid]:\r\n            return mid\r\n        elif a[mid] > x:\r\n            l = mid-1\r\n        else:\r\n            r = mid+1\r\n    return -1\r\n\r\n\r\n# Grafh related queries : \r\n\r\n\r\n\r\ngraph = defaultdict(list)\r\nvisited = [0] * 1000000\r\ncol = [-1] * 1000000\r\n \r\n \r\ndef bfs(d, v):\r\n    q = []\r\n    q.append(v)\r\n    visited[v] = 1\r\n    while len(q) != 0:\r\n        x = q[0]\r\n        q.pop(0)\r\n        for i in d[x]:\r\n            if visited[i] != 1:\r\n                visited[i] = 1\r\n                q.append(i)\r\n        print(x)\r\n \r\n \r\ndef make_graph(e):\r\n    d = {}\r\n    for i in range(e):\r\n        x, y = mi()\r\n        if x not in d:\r\n            d[x] = [y]\r\n        else:\r\n            d[x].append(y)\r\n        if y not in d:\r\n            d[y] = [x]\r\n        else:\r\n            d[y].append(x)\r\n    return d\r\n \r\n \r\ndef gr2(n):\r\n    d = defaultdict(list)\r\n    for i in range(n):\r\n        x, y = mi()\r\n        d[x].append(y)\r\n    return d\r\n \r\n \r\ndef connected_components(graph):\r\n    seen = set()\r\n \r\n    def dfs(v):\r\n        vs = set([v])\r\n        component = []\r\n        while vs:\r\n            v = vs.pop()\r\n            seen.add(v)\r\n            vs |= set(graph[v]) - seen\r\n            component.append(v)\r\n        return component\r\n \r\n    ans = []\r\n    for v in graph:\r\n        if v not in seen:\r\n            d = dfs(v)\r\n            ans.append(d)\r\n    return ans\r\n\r\n# End graph related queries\r\n \r\n#### PRIME FACTORIZATION IN O(log n) using Sieve ####\r\nMAXN = int(1e6 + 5)\r\ndef spf_sieve():\r\n    spf[1] = 1;\r\n    for i in range(2, MAXN):\r\n        spf[i] = i;\r\n    for i in range(4, MAXN, 2):\r\n        spf[i] = 2;\r\n    for i in range(3, ceil(MAXN ** 0.5), 2):\r\n        if spf[i] == i:\r\n            for j in range(i*i, MAXN, i):\r\n                if spf[j] == j:\r\n                    spf[j] = i;\r\n    ## function for storing smallest prime factors (spf) in the array\r\n \r\n################## un-comment below 2 lines when using factorization #################\r\n# spf = [0 for i in range(MAXN)] \r\n# spf_sieve() \r\ndef factoriazation(x):\r\n    ret = {};\r\n    while x != 1:\r\n        ret[spf[x]] = ret.get(spf[x], 0) + 1;\r\n        x = x//spf[x]\r\n    return ret\r\n    ## this function is useful for multiple queries only, o/w use\r\n    ## primefs function above. complexity O(log n)\r\n \r\n## taking integer array input\r\n\r\n\r\n# LCM of two numbers :\r\ndef lcm(a, b): return abs(a * b) // math.gcd(a, b)\r\n \r\n#defining a couple constants\r\nMOD = int(1e9)+7;\r\nCMOD = 998244353;\r\nINF = float(\'inf\'); NINF = -float(\'inf\');\r\ny, n = "YES", "NO"\r\nabd = {\'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,\r\n       \'n\': 13, \'o\': 14, \'p\': 15, \'q\': 16, \'r\': 17, \'s\': 18, \'t\': 19, \'u\': 20, \'v\': 21, \'w\': 22, \'x\': 23, \'y\': 24,\r\n       \'z\': 25}\r\n\r\n\r\n# used for testing your code \r\n\r\n# inputs=open(\'input.txt\',\'r\') \r\n\r\ndef solve():\r\n    # n = no. of lines,c = no. of distinct color ,k = len. of erasor \r\n    n,c,k = map(int,input().split())\r\n    d = {}\r\n    for i in range(n):\r\n        a,b,c = map(int,input().split())\r\n        if c not in d.keys():\r\n            d[c] = 1\r\n        else:\r\n            d[c] += 1\r\n    v = list(map(int,input().split())) # equal \r\n    l_r = k//v[0] # how much line can i remove\r\n    l = list(d.values())\r\n    i = 0\r\n    while l_r != 0:\r\n        l[l.index(max(l))] -= 1\r\n        l_r -= 1 \r\n    count = 0\r\n    for i in l:\r\n        count+=((i)*(i-1)*(i-2))//6\r\n    print(count)\r\ndef __starting_point():\r\n    # solve()\r\n    # for t in range(getint()):\r\n    #     print("Case #{}: ".format(t + 1), end="")\r\n    #     solve()\r\n    for _ in range(int(input())):#getint()):\r\n        solve()\r\n\r\n    # https://codeforces.com/contest/507/status/B/page/296?order=BY_PROGRAM_LENGTH_ASC\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 16026443