Optimal Placement of Elementary Schools

On one side of a long road, there are many buildings, and each building has a number of elementary school students. Strangely, there is no elementary school along this road! Niu A, in his eccentric desire to create chaos, has decided to build K elementary schools at any chosen points on the road (these points can coincide with the buildings' positions or not) such that the total walking distance for all the students to their nearest school is minimized.

Given the positions of the buildings and the number of students in each building, your task is to determine the minimum total distance all students need to travel when K schools are optimally placed.

Note: The optimal school location for a group of buildings is the weighted median of the positions in that group, which minimizes the weighted sum of absolute deviations. The solution involves dynamic programming in conjunction with precomputed costs for intervals.

inputFormat

The first line contains two integers n and K, where n is the number of buildings and K is the number of schools to be built. Each of the following n lines contains two integers p and s, where p is the position of a building on the road and s is the number of students in that building.

outputFormat

Output a single integer representing the minimum total distance that all students need to travel to reach the nearest school.

sample

3 1
1 10
3 5
6 3

25