410063: GYM103934 K Railways

Egypt's railway system is one of the oldest in the world and is one of the most used transport modals in the country. Due to this tradition, some cities organize themselves completely along the train lines. Consider a railway as a straight line that extends from point zero to $$$10^9$$$ meters, and a city is organized along this train line.

There are $$$N$$$ inhabitants in this city who need to go to work. The $$$i$$$-th inhabitant lives at point $$$X_i$$$ (meters from point zero), works at point $$$Y_i$$$, different from where they live, and their shift starts at time $$$T_i$$$ seconds.

At zero time, all citizens leave home to work. Citizens walk at a speed of 1 meter per second. As the bosses in Egypt are very strict, if an employee is late by any epsilon, they will be fined $$$V_i$$$ Egyptian pounds.

At time zero, a train leaves point zero and travels through the city at $$$B$$$ meters per second. This train stops at every integer point. The time it takes to board and disembark passengers is negligible.

A train ticket costs $$$P$$$ Egyptian pounds.

It is well known that if a person walks to work and is not fined, they will not pay for the ticket. It is also known that a person will never be willing to lose more money than they need to, hence if going by train avoids the fine, the person will pay for the ticket only if its cost does not exceed the fine.

ENR (Egyptian National Railways) is looking to maximize the company's profit (the sum of fares paid). Given a list of $$$N$$$ residents with the above information, determine the value of $$$P$$$ that maximizes the company's profit. If multiple answers maximize profit, print the cheapest one.

The first line contains two space separated integers $$$N$$$ ($$$1 \leq N \leq 2.10^5$$$) and $$$B$$$ $$$(1 \leq B \leq 10)$$$. The next $$$N$$$ lines contain four space separated integers each $$$X_i, Y_i, T_i, V_i$$$$$$(1 \leq X_i, Y_i, T_i, V_i \leq 10^9)$$$. It is guaranteed that $$$X_i \neq Y_i$$$ for all $$$1 \leq i \leq N$$$.

One integer, the train fare that maximizes the profit. If there are multiple answers, print the cheapest one.

3 3
3 6 2 10
7 9 1 5
1 3 1 1

10

1 10
5 7 2 9

0

3 10
1 3 1 4
2 4 1 5
3 5 1 12

4