Problem Description

Yazid is going to listen to reports from $n$ people today. For convenience, we number these people from $1$ to $n$.

Yazid has an excitement level, initially set to $s$, which changes as the reports progress.

The report of the $i$-th person ($1 \leq i \leq n$) can be described by three numbers $a_i, b_i, c_i$. This means that if Yazid's excitement level is $x$ before listening to his report, it will become $a|x| + bx + c$ after listening to his report.

Yazid also needs to attend a final exam, so he hopes to be as excited as possible after the reports. Therefore, your task is to help Yazid determine the order of the reports to maximize his excitement level after all reports.

Input Format

The first line contains two integers $n$ and $s$ separated by a space.

The next $n$ lines describe the reports of the $n$ people. The $i$-th line contains three integers $a_i, b_i, c_i$ separated by spaces.

Output Format

Output a single integer, which represents the maximum excitement level of Yazid after all reports.

Sample Input and Output

Sample Input #1

2 3
0 1 1
0 2 0

Sample Output #1

8

Sample Input #2

1 -2
8 -4 1

Sample Output #2

25

Notes/Hints

[Sample Explanation #1]

If Yazid listens to the first person's report first, followed by the second person's report, the final excitement level is $(3 + 1) \times 2 = 8$.

If Yazid listens to the second person's report first, followed by the first person's report, the final excitement level is $(3 \times 2) + 1 = 7$.

Thus, the maximum excitement level is $8$.

[Sample Explanation #2]

There is only one report. Yazid's initial excitement level is $-2$, and after listening to the report, his excitement level becomes $8 \times |-2| + (-4) \times (-2) + 1 = 25$.

[Subtasks]

Subtask 1 (13 points): $n \leq 10$;

Subtask 2 (19 points): $c_i = 0$;

Subtask 3 (23 points): $a_i = 0$;

Subtask 4 (45 points): No additional constraints.

For all test cases, it is guaranteed that $n \leq 15$, and the absolute values of $a, b, c, s$ do not exceed $15$.

[Hint]

Given the data constraints, the answer will not exceed the range of a 128-bit signed integer, so you can try using __int128 to help implement your algorithm.

见题面 Input 部分

见题面 Output 部分