Hello to whoever may be reading this, have a good morning, good afternoon or good night. I've been involved in competitive programming for 2, almost 3 years now, and although it's been a little over a year since I registered for Codeforces, I've barely used it. And I have seen several problems throughout all this time. But there is one in particular that from the moment it was published on the page that we use in our country to carry out competitions and training, with a view to international Olympics like the IOI (https://dmoj.uclv.edu.cu) has caught my attention a lot. attention, because no one, not even those who I consider the most top programmers in my country have been able to solve, this problem is titled "Elevator system for a hotel" (https://dmoj.uclv.edu.cu/problem/2023copa10b) (our page only has the Spanish language, in case you want to take a look at the problem for yourselves, I still leave you the English translation)

And the problem says:

You've been hired to build an elevator system for a hotel! The hotel has k elevators, and initially you can choose which floors they are on. During the day there are n requests, each characterized by a pair (l, r). This means that someone is on floor l and wants to go to floor r. People don't like to wait, so we have a requirement to complete requests sequentially. More formally, request number i must behave before request number i+1. Elevators are small and must be empty or carry exactly one passenger at any given time. Additionally, any request can be completed by any elevator. We want to build a smart system, so we want to minimize the total number of floors when the elevators travel empty. More precisely, if an elevator travels without passengers from floor p to floor q, then we consider that it has traveled |p-q| empty floors.

Input:

The first line contains the numbers n and k, representing the number of requests and lifts respectively The next n lines contain 2 integers (l, r) representing each request respectively

Output:

It will only contain a number representing the minimum sum of floors where the elevators travel empty.

Restrictions:

1 ≤ n ≤ 10⁴

1 ≤ k ≤ min(30, n)

1 ≤ l, r ≤ 10⁹

Entry example:

3 2

5 20

8 100

2 80

Output example:

12

Example explanation:

Elevator 1 is originally on the 5th floor and elevator 2 is on the 8th floor Elevator 1 travels 0 empty floors 0 empty floors and drops the passenger on the 20th floor. It then travels 12 empty floors to the 8th floor, where it picks up the passenger and travels 0 empty floors to the 100th floor. Finally the 2nd elevator travels 0 floors empty up to the 80th floor. Then the total number of floors where the elevators travel empty is 0+12+0=12

And what I'm looking for here is someone who can help me with this, explaining how to solve the problem, whoever would be so kind as to help me, I would be very grateful. Without much more to say, I thank you once again for your attention and I await a response, greetings and I hope we all continue to grow together <3