Description

Recently, Xiao A became obsessed with playing the game “Gold Miner” during class. To avoid being noticed by the teacher, he has to be very cautious, so he always loses.

After losing all his coins, he asks you for help. Each piece of gold can be regarded as a point (no volume). You are given the coordinates of $N$ pieces of gold, the time required to mine each, and their value. Some pieces of gold lie on the same straight line; in that case, you must mine them in order. You can instantly rotate the hook to any angle.

Xiao A starts at coordinate $(0, 0)$. Please help Xiao A compute the maximum total value he can obtain within time $T$.

Input Format

The first line contains two integers $N$ and $T$, the number of gold pieces and the total time.

The next $N$ lines each contain four integers $x$, $y$, $t$, $v$, denoting the coordinates of a piece of gold, the time to mine it, and its value.

Output Format

Output a single integer, the maximum total value obtainable within time $T$.

3 10
1 1 1 1
2 2 2 2
1 3 15 9

3

3 10
1 1 13 1
2 2 2 2
1 3 4 7

7

Hint

• For $30\%$ of the testdata, $0 < T \le 4 \times 10^3$.
• For $100\%$ of the testdata, $1 \le N \le 200$, $0 < T \le 4 \times 10^4$.

It is guaranteed that $0 \le |x| \le 200$, $0 < y \le 200$, $0 < t \le 200$, $0 \le v \le 200$.

Translated by ChatGPT 5