School Bus

Several apartment complexes lie on a straight road, and a school is located at another point on the same road. For each apartment complex, its coordinate and the number of students living there are given.

There is exactly one school bus. On each trip, the bus starts at the school, picks up students from apartment complexes, and returns to the school. The bus can carry at most K students at a time, and it repeats trips until every student has reached school. The distance between two points is the absolute difference of their coordinates.

Given the school coordinate, the apartment coordinates, the number of students at each apartment, and the bus capacity, compute the minimum possible total distance traveled by the bus.

The first line contains three positive integers N, K, and S separated by spaces.

• N is the number of apartment complexes, where 2 <= N <= 30,000.
• K is the bus capacity, where 1 <= K <= 2,000.
• S is the coordinate of the school.

Each of the next N lines contains the coordinate of an apartment complex and the number of students living there. The school coordinate and all apartment coordinates are between 0 and 100,000, inclusive, and are all distinct. The number of students in each complex is between 1 and 2,000, inclusive.

Print one line containing the minimum total distance the bus must travel to bring all students to school. The minimum distance is guaranteed not to exceed 1,000,000,000.