32157번 - 한요원의 잠입

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

언젠가 누군가가 풀이를 훔칠 것을 예상한 대학교는 $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}$)

풀이를 가져올 수 있는 최소 시간을 초 단위로 출력한다. 한요원은 엄청난 잠입 천재임과 동시에 엄청난 탈출 천재이기 때문에 나가는 시간은 고려할 필요가 없다.