Problem Description

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

Yazid has an excitement level, initially $s$, and this value will change as the reports go on.

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

Yazid also needs to take final exams, so he wants to be as excited as possible after listening to all the reports. Therefore, your task is to help Yazid decide the order of all reports so that Yazid’s excitement level is maximized after everyone has finished presenting.

Input Format

The first line contains two integers $n,s$ separated by spaces.

The next $n$ lines describe the $n$ people’s reports. Line $i$ of this part contains three integers $a_i,b_i,c_i$ separated by spaces.

Output Format

Output one integer in one line, representing the maximum excitement level Yazid can have after listening to all the reports.

2 3
0 1 1
0 2 0

8

1 -2
8 -4 1

25

Hint

[Sample Explanation #1]

If Yazid listens to the first person’s report first, and then the second person’s report, the final excitement level is $(3+1)\times2=8$.

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

So the maximum excitement level is $8$.

[Sample Explanation #2]

There is only one report. Yazid’s initial excitement level is $-2$, so after listening to the report, the excitement level is $8\times \lvert -2 \rvert+(-4)\times (-2)+1=25$.

[Subtasks]

Subtask 1 (13 points): $n \le 10$.

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

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

Subtask 4 (45 points): no special constraints.

For all testdata, it is guaranteed that $n\leq 15$, and the absolute values of $a,b,c,s$ are all at most $15$.

[Hint]

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

Translated by ChatGPT 5