한요원의 잠입

한요원은 엄청난 코딩 천재이다. 열심히 문제를 풀던 한요원은 어느 날 본인이 풀 수 없는 문제를 만나 난관에 봉착했다. 그런데 그 문제의 풀이가 적힌 종이가 통합된 신촌 지역 대학교에 숨겨져 있다는 사실을 들었다. 따라서 한요원은 대학교에 잠입해 풀이를 훔쳐 오기로 결심했다.

누군가 풀이를 훔칠 것을 예상한 대학교는 $N+1$개의 건물을 잇는 $N$개의 통로마다 엄청난 경비를 배치해 놓았다.

한요원은 잠입을 시작하는 1번 건물에서 통로를 따라 풀이가 있는 $N+1$번 건물까지 가려고 한다. 경비에게 들키지 않고 통로 하나를 통과하는 방법은 아래 세 가지 중 하나를 쓸 수 있다.

1. 들키지 않고 $s_i$초를 소비하여 $i$번 건물에서 $i+1$번 건물로 이동한다.
2. 소리를 내며 $l_i$초를 소비하여 $i$번 건물에서 $i+1$번 건물로 이동한다.
3. 텔레포트를 사용해 0초를 소비하여 $i$번 건물에서 $i+1$번 건물로 이동한다.

들키지 않고 지나가면 한요원이 발각될 일은 없다. 반면 소리를 내며 빠르게 지나가면 들킬 위험이 크게 높아진다. 대학교를 통과하는 동안 소리를 낸 횟수가 $W$번을 넘으면 경보가 울려 풀이를 가져오지 못한다. 즉, 한요원은 대학교에 있는 동안 소리를 최대 $W$번까지 낼 수 있다.

텔레포트를 쓰면 들키지 않고 다음 건물로 무사히 넘어갈 수 있다. 다만 텔레포트는 힘이 많이 들어서 대학교 안에서 최대 $T$번만 쓸 수 있다.

한요원은 $N+1$번 건물에 도착하는 순간 0초 만에 풀이를 얻을 수 있다.

첫 번째 줄에는 통로의 수 $N$, 소리를 낼 수 있는 최대 횟수 $W$, 텔레포트를 쓸 수 있는 횟수 $T$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 3 \times 10^{5};$ $0 \leq W \leq N;$ $0 \leq T \leq N$)

두 번째 줄부터 $N+1$번째 줄까지는 각 통로를 들키지 않고 지나갈 때 걸리는 시간 $s_i$와 소리를 내며 지나갈 때 걸리는 시간 $l_i$가 공백으로 구분되어 주어진다. ($1 \leq s_i, l_i \leq 10^{12}$)

풀이를 가져올 수 있는 최소 시간을 초 단위로 출력한다. 한요원은 잠입과 탈출 모두에 천재이므로 나가는 시간은 고려하지 않는다.