A long way back I have taken $5000 from Golu when I used to live in Jodhpur. Now, time has passed and I am out of Jodhpur. While Golu still in Jodhpur, one day called me and asked about his money.
I thought of giving Golu a chance. I told him that he can still take his money back if he reaches my home anyhow just in 2 days but not after that. 
In excitement he made his way toward my hometown i.e. Gorakhpur. To cover up the petrol cost he started giving paid lift to whoever needs it throughout the way in order to earn some money. Help him to get the maximum profit.

His car has a capacity of k + 1 person, so in a certain moment he can transport k persons (and himself). 
From Jodhpur to Gorakhpur, there are l localities (cities, towns, villages), Jodhpur being the first and Gorakhpur being the lth.
There are n groups of lift takers along the road. The ith
group consists of pi persons, wants to travel from locality si  to locality di and will pay an amount of mi money.
A group must be taken into the car as a whole. Assume that lift takers are found only in localities.

Restrictions
• 1 ≤ k ≤ 7
• 1 ≤ l ≤ 1000000
• 1 ≤ n ≤ 50
• 1 ≤ pi ≤ k
• 1 ≤ si ≤ l – 1
• 2 ≤ di ≤ l
• si < di
• 1 ≤ mi ≤ 1000000

-----Input-----
The first line of the input contains the number of test cases.
The first line of each test case contains the numbers n, l and k separated by a single space.
n lines follow, the ith line containing pi, si, di and mi separated by a single space.


-----Output-----
For each test case output a single line containing the maximum amount of money Golu can earn.

-----Example-----
Input:
2
5 5 4
2 1 5 50
1 2 4 20
2 3 4 40
2 4 5 50
3 4 5 80
10 10 5
2 5 10 17300
2 1 8 31300
5 4 10 27600
4 8 10 7000
5 9 10 95900
2 7 10 14000
3 6 10 63800
1 7 10 19300
3 8 10 21400
2 2 10 7000

Output:
140
127200

By:
Chintan, Asad, Ashayam, Akanksha

```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 = '\'\'\'Well I found the bug, but I don\'t understand why it was doing that. I mean, as\nfar as I can tell, it shouldn\'t be a bug!\nNote to self: deleting from (supposedly) local lists through recursion is dangerous!\'\'\'\n\nclass Group(object):\n    def __init__(self,size,start,end,value):\n        self.size = size\n        self.start = start\n        self.end = end\n        self.value = value\n        \n    def __lt__(self,other):\n        return self.start < other.start\n    \n    def __str__(self):\n        return "%i: %i->%i, $%i" %(self.size,self.start,self.end,self.value)\n    \n    \ndef hash(car,i):\n    people = []\n    for group in car:\n        people.extend([group.end]*group.size)\n    people.sort()\n    return tuple(people+[i])\n    \n    \ndef optimize(groups,car,capacity,i):   \n    if i == len(groups):\n        return 0\n    \n    newcar = []\n    pos = groups[i].start\n    for group in car:\n        if group.end > pos:\n            newcar.append(group)\n        else:\n            capacity += group.size\n        \n    state = hash(newcar,i)\n    try:\n        return memo[state]\n    except:\n        v = optimize(groups,newcar,capacity,i+1) \n        if groups[i].size <= capacity:\n            w = optimize(groups,newcar+[groups[i]],capacity-groups[i].size,i+1) + groups[i].value\n        else:\n            w = 0\n            \n        if v > w:\n            ie[state] = -1\n        elif v < w:\n            ie[state] = 1\n        else:\n            ie[state] = 0\n                \n        ans = max(v,w)\n        memo[state] = ans\n        return ans\n    \ncases = int(input())\nfor case in range(cases):\n    memo = {}\n    ie = {}\n    groups = []\n    n,_,capacity = list(map(int,input().split()))\n    \n    for g in range(n):\n        size,start,end,value = list(map(int,input().split()))\n        groups.append(Group(size,start,end,value))\n    groups.sort()\n    print(optimize(groups,[],capacity,0))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 25969