409173: GYM103449 A Mountains
Description
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.
InputThe 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)$$$.
OutputPrint 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.
Scoring- 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 250Output
3 101Input
5 1 1000 0 1000 3000 -1000 0 5000 0 1000 7000 -1000 0 9000 -9000 0Output
3 2Input
7 0 2000 -1000 1000 1000 -1000 1000 3000 -1000 1000 1000 -1000 1000 4000 -1000 1000 2000 -1000 1000 3000 -1000 1000Output
2 3Note
- 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$$$.