Venus Rover

After NASA sent its Mars exploration rovers Spirit and Opportunity to Mars, ASAN decided to send its Venus exploration rover Greedy to Venus to find out which valuable raw resources can be obtained there. Greedy's mission is to collect stones from the surface of Venus.

Greedy is carried to Venus by a rocket. The rocket drops Greedy onto the surface together with a large container, flies seven times around Venus, and finally picks up both Greedy and the container with its on-board grabbers.

After landing, Greedy uses its IntelliSensor technology to scan for every interesting stone within half a mile. This produces a list of stones, each with an accurate estimate of its mass, its value, and the time needed to pick it up and place it in the container. The container is large enough to hold all of the stones, but the rocket can lift only a limited amount of mass from the surface. The available time is also limited, because the rocket returns after its seven laps around Venus.

Your task is to write a program that decides which stones to pick up and place in the container so that the total value is maximized.

The first line contains the number of test cases. Each test case has the following format.

• A line with three positive integers $N$, $T$, and $M$. Here $0 < N \le 100$ is the number of stones found, $0 < T \le 100$ is the time available before the rocket returns to collect Greedy and the container, and $0 < M \le 100$ is the maximum mass of stones the rocket can lift.
• Then $N$ lines follow; the $i$-th line contains three positive integers $t_i$, $m_i$, and $v_i$ (all at most $10^6$), giving respectively the time required to pick up stone $i$, its estimated mass, and its estimated value.

For each test case, print on a single line a single integer: the maximum total value that can be collected in that test case.