Gold Digger's Dilemma

Little A has recently become addicted to playing Gold Miner in class. To avoid being caught by the teacher, he always plays very cautiously, and as a result, always loses. After losing all his coins, he asks for your help.

There are N gold pieces. Each gold can be considered a point (with no volume). For each piece of gold, you are given its coordinates \( (x,y) \), the time \( t \) required to extract it, and its value \( v \). Note that some gold pieces lie on the same ray (line radiating from the origin). When gold pieces are collinear with the origin, you must extract them in order of increasing distance from \( (0,0) \); that is, if you want to extract a piece that is farther along the same ray, you must have already extracted all gold pieces that lie closer along that ray.

The hook can be instantly rotated to any angle. Starting from \( (0,0) \), determine the maximum total gold value that Little A can obtain within \( T \) units of time.

Note: For gold pieces on the same ray, you must take them in order (from the closest to the furthest) if you decide to collect any from that ray.

Hint: Group the gold pieces by their ray (i.e. by their direction from \( (0,0) \)), compute the prefix sums of the digging times and values in each group, and then use a knapsack-style dynamic programming approach to select an optimal combination from different groups.

inputFormat

The first line contains two integers \( N \) and \( T \) separated by a space, where \( N \) is the number of gold pieces and \( T \) is the total available time.

Each of the next \( N \) lines contains four integers: \( x \), \( y \), \( t \), and \( v \) which represent the coordinates of a gold piece, the time required to extract it, and its value respectively.

You may assume that \( (x,y) \) ≠ \( (0,0) \).

outputFormat

Output a single integer representing the maximum total value of gold that can be obtained within time \( T \).

sample

3 10
1 1 3 5
2 2 4 10
0 1 2 4

19