Bounty Hunter

N thieves escaped into an infinitely large two-dimensional plane.

Bounty hunter Muji has T time left and wants to catch as many thieves as possible to collect the bounties on them.

Each thief starts at an integer coordinate point and moves at speed 1 for one hour in only one initial direction, chosen from east, south, west, or north.

Muji moves at the same speed as a thief, but can change to any of the four directions at any time. Muji may also stay in place.

The X coordinate increases toward the east, and the Y coordinate increases toward the north.

If Muji and a thief are at the same position at the same time, Muji spends 1 hour to catch that thief at that position and earns the bounty $C_i$. Muji cannot catch two or more thieves at once. The position may have real-valued coordinates.

Muji starts at the origin (0,0). Find the maximum total bounty Muji can earn within the remaining time T.

The first line contains the number of thieves $N$ and the remaining time $T$, separated by a space. ($1 \le N \le 500$, $1 \le T \le 1\,000$)

From the second line through line $N+1$, each line contains the thief's initial position $X_i$, $Y_i$, bounty $C_i$, and direction $D_i$, separated by spaces. ($-2\,000 \le X_i \le 2\,000$, $-2\,000 \le Y_i \le 2\,000$, $1 \le C_i \le 500\,000$, $0 \le D_i \le 3$)

The thief moves east if $D_i$ is 0, south if 1, west if 2, and north if 3.

Print the maximum total bounty Muji can collect by catching thieves within the remaining time $T$.

Muji always moves parallel to the $X$ axis or the $Y$ axis.