## Bus Stops

If you take the TTC, you'll know that often buses can only carry a certain number of people (call this C).Sometimes, you get left stranded at the bus stop when the bus is full.

If you're lazy, you'll just wait for the next bus. But sometimes, it might just be better to walk to another stop beforehand.

In our scenario, there is only one bus, and so some people might be required to walk.

Let's suppose you know in advance all N of the passengers and where they want to get on and off.

Now, you want to create a plan so that each passenger spends the least amount of time in transit to reach his/her destination.

All passengers are treated equally - we just want to minimize the

**total**time for all passengers.

The bus starts at bus stop #1 and goes "rightward", going to bus stop 2, then 3, etc.

The bus stops, numbered 1,2,3 ... B, are located along a perfectly straight street.

It takes 5 minutes to walk from one bus stop to the next, and 1 minute to do the same by bus.

### Input

Three integers, passengers (**N**) ≤ 1,000,000, stops (

**B**) ≤ 1,000,000, capacity (

**C**) ≤ N

N pairs of integers, representing the start and end stops of a passenger.

Passengers get to their starting stops instantly.

Assume that they get to their required bus stop right on time: they won't have to wait for the bus.

All numbers will be positive integers.

### Output

The total time taken for all the passengers to get to work, assuming an optimal schedule.### Sample Input

3 5 2 1 5 2 5 3 4

### Sample Output

12

The bus only holds 2 people, so the third guy has to walk. (No passenger is favored over another)

*Passenger 1:*takes the bus (4 minutes)

*Passenger 2:*takes the bus (3 minutes)

*Passenger 3:*walks from 3-4 (5 minutes)

### Sample Input

5 8 1 1 3 2 4 2 5 6 7 7 8

### Sample Output

21

In this case, the bus is more like a taxi.

*Passenger 1:*Just takes the bus (2 minutes)

*Passenger 2:*walks to stop 3 first (5 minutes) and then takes the bus to 4 (1 minute)

*Passenger 3:*walks to stop 4 first (10 minutes) and then takes the bus to 5 (1 minute)

*Passengers 4/5:*just take the bus (1+1 minutes)

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Nov 02, 2008

**Author:** hansonw1

**Problem Types:**[Show]

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

wjomlexon Nov 02, 2011 - 3:42:35 pm UTC Bounds for Javabbi5291on Nov 03, 2011 - 3:40:58 pm UTC Re: Bounds for JavaOur current policy is basically to ignore the fact that Java exists at all, mostly because it's a lot harder to grade Java programs accurately than it is to grade C/C++/Pascal ones. This may change if they ever start allowing Java at the IOI, but according to kolstad it's not likely to happen soon, as it gets proposed (and subsequently rejected) every year.

(NB: kolstad also implied that the only reason why Java is allowed in USACO is that it's unreasonably popular among Americans. He's probably also one of very few people in the world with enough technical expertise to grade it properly.)

frenzybenzyon Nov 30, 2008 - 4:48:46 pm UTC i dont get it....hansonw1on Nov 29, 2008 - 8:12:53 pm UTC QuestionOr was it just too hard? (It's not too bad, the solution is very simple)