Bus

Every morning Anton takes the bus to work.

The bus route has $n$ stops, numbered from $1$ to $n$ in the order they are visited. The bus takes one minute to travel from each stop to the next, and its stopping time can be ignored. Anton boards at the first stop and gets off at the last one.

The bus has $m$ seats arranged in a single row and numbered from $1$ to $m$; the seat closest to the entrance is number $1$, and the farthest is number $m$. Each seat can hold one seated passenger, and one passenger can stand next to each seat.

When a person boards the bus, they sit in the free seat closest to the entrance. If all seats are taken, they look for the seat closest to the entrance that has no one standing next to it and stand over the person sitting there. If no such place exists, they get off the bus.

Every passenger stays in their place until the bus reaches their destination stop. A standing passenger keeps standing even if a seat becomes free.

At each stop, all passengers who intended to get off there leave the bus first, and only then do new passengers board.

Anton boarded the bus first, and he can sit in any seat and stay there until the end of the trip. He knows exactly who else will ride the bus: for every passenger, Anton knows at which stop they will board and at which stop they will get off. Help Anton choose a seat so that, over the course of the trip, the total time during which someone stands over him is as small as possible.

The first line of the input contains three integers $n$, $m$, and $k$: the number of stops, the number of seats on the bus, and the number of passengers other than Anton ($2 \le n \le 10^9$, $1 \le m \le 2\cdot10^5$, $0 \le k \le 2\cdot10^5$).

The next $k$ lines each contain two numbers $a\_i$ and $b\_i$, meaning that the $i$-th passenger intends to board at stop $a\_i$ and get off at stop $b\_i$ ($1 \le a\_i < b\_i \le n$).

If several people board the bus at the same stop, they board in the order in which they are listed in the input.

Output two numbers on one line: the minimum total time in minutes during which someone stands over Anton, and the number of the seat he must take to achieve it. If there are several such seats, output the one closest to the entrance.