409173: GYM103449 A Mountains

In the wonderful mountain ranges of the United States of Berland there are $$$n$$$ peaks. Each peak is characterized by 3 integers: $$$h$$$, $$$l$$$ and $$$r$$$. Peak $$$i$$$ is currently $$$h_i$$$ meters tall and its height can vary within a year by any integer $$$\Delta h \in [l_i,r_i]$$$.

Formally, if at the start of year $$$k$$$ the height of peak $$$i$$$ was $$$h_k$$$, at the end of that year the height of peak $$$i$$$ can be any integer in the interval $$$[h_k+l_i,h_k+r_i]$$$. It is possible for some peaks to reach negative heights (aka become sinkholes) after some time.

For each mountain $$$i$$$ you are given $$$h_i$$$, $$$l_i$$$ and $$$r_i$$$. Find the maximum possible number of peaks with equal heights at the beginning of year $$$y$$$ and the number of distinct heights reachable by this maximum number of peaks.

The first line of input contains two integers $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$, the number of peaks and $$$y$$$ $$$(0 \le y \le 10^9)$$$, the number of years. Each of the next $$$n$$$ lines of input contain 3 integers $$$h_i,l_i$$$ and $$$r_i$$$, describing the peaks $$$(-10^9 \le l_i \le r_i \le 10^9$$$ and $$$1 \le h_i \le 10^9)$$$.

Print two integers, the maximum number of peaks that can reach the same height after $$$y$$$ years, and the number of distinct heights that can be reached by the maximum number of peaks.

• Subtask 1 (10 points): $$$y=0$$$;
• Subtask 2 (30 points): $$$1 \le n,y \le 100$$$, $$$-100 \le l_i \le r_i \le 100$$$, $$$1 \le h_i \le 100$$$;
• Subtask 3 (20 points): $$$y=1$$$;
• Subtask 4 (40 points): No further constraints.

3 2
3000 -250 600
4000 0 50
5000 -500 250

3 101

5 1
1000 0 1000
3000 -1000 0
5000 0 1000
7000 -1000 0
9000 -9000 0

3 2

7 0
2000 -1000 1000
1000 -1000 1000
3000 -1000 1000
1000 -1000 1000
4000 -1000 1000
2000 -1000 1000
3000 -1000 1000

2 3

• In the first sample, the three peaks can reach any of the heights from $$$4000$$$ to $$$4100$$$, in total $$$101$$$ possible heights.
• In the second sample, the peaks indexed $$$1,2$$$ and $$$5$$$ can reach height $$$2000$$$, and the peaks indexed $$$3,4$$$ and $$$5$$$ can reach height $$$6000$$$.
• In the third sample, $$$y=0$$$, and there are two peaks with each of the heights $$$1000$$$, $$$2000$$$ and $$$3000$$$.