Maximizing Excitement

Yazid is scheduled to listen to n presentations. For convenience, the speakers are numbered from \(1\) to \(n\). Initially, Yazid's excitement is \(s\). The \(i\)th presentation (\(1 \le i \le n\)) is described by three integers \(a_i\), \(b_i\), \(c_i\). If before a presentation Yazid's excitement is \(x\), then after listening to the presentation his excitement becomes

[ f_i(x)=a_i\lvert x\rvert+b_i,x+c_i, ]

Your task is to arrange the order in which Yazid listens to all the presentations so that his final excitement is maximized after all presentations have been given.

Note: Since the number of speakers is small (\(n\) is at most 10), a brute force solution that considers all \(n!\) orders is acceptable.

inputFormat

The input begins with a line containing two integers \(n\) (the number of presentations, \(1 \le n \le 10\)) and \(s\) (the initial excitement of Yazid).

Then follow \(n\) lines, each containing three integers \(a_i\), \(b_i\), and \(c_i\), describing the \(i\)th presentation.

outputFormat

Output a single integer representing the maximum final excitement that can be achieved after scheduling all the presentations in an optimal order.

sample

1 0
1 1 1

1