Optimal Meeting Points in Blue Bridge Village

In Blue Bridge Village, all residents live along a road of length \(L\). The position of each household is given by its distance \(d_i\) from the starting point of the road, and each house has \(t_i\) residents.

Every year a gathering is held in the village. This year, due to the large population, the village committee has decided to hold four gatherings in total: three gatherings at positions along the interior of the road and one gathering at the road's end. Let the meeting points be \(p_1, p_2, p_3, p_4\) such that \(p_1 \le p_2 \le p_3 \le p_4 = L\).

Every household travels in the direction away from the starting point (i.e. in increasing order of distance) to attend the meeting. Each household will attend the first meeting location whose position is not less than the household's position. The travel cost for a household is defined as the product of its number of residents and the distance it travels to the meeting point. That is, if household \(i\) attends a meeting held at \(p_j\), its cost is \(t_i \times (p_j - d_i)\).

Your task is to choose \(p_1, p_2, p_3\) (with \(p_4\) fixed at \(L\)) to minimize the total travel cost of all residents in the village.

Hint: For a group of households with positions \(d_l, d_{l+1}, \ldots, d_r\) that all attend the same meeting (with the meeting point chosen as \(d_r\)), the total cost for the group is

\[ \text{cost}(l, r) = d_r \sum_{i=l}^{r} t_i - \sum_{i=l}^{r} t_i d_i. \]

For the households that attend the meeting at \(p_4 = L\), the cost for a group is calculated using \(L\) instead of \(d_r\). Use appropriate dynamic programming techniques to partition the households into four (possibly consecutive) groups.

inputFormat

The first line contains two integers \(n\) and \(L\) where \(n\) is the number of households and \(L\) is the length of the road.

Each of the following \(n\) lines contains two integers \(d_i\) and \(t_i\) representing the position of the \(i\)-th household and the number of residents in that household.

Note that the households may be given in arbitrary order.

outputFormat

Output four space-separated numbers \(p_1, p_2, p_3, p_4\) representing the chosen meeting positions. The first three meeting points can be chosen optimally (subject to \(p_1 \le p_2 \le p_3\)) and \(p_4\) is fixed to \(L\).

If there are multiple optimal solutions, output any one of them.

sample

4 10
1 2
2 3
3 4
9 5

2 3 9 10