시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)43719916150.312%

문제

학생 $N$명이 미술 대회에 참가하였다. 이 대회에서는 주최자 한 명과 심판 한 명이 수상자를 결정하며, 수상자 결정 방식은 다음과 같다.

  1. 주최자와 심판이 각자 모든 학생들의 작품에 점수를 매긴다. 두 사람 모두 점수를 매길 때 서로 다른 두 작품에 같은 점수를 주지 않는다.
  2. 주최자가 $M$명의 학생을 골라 특별상을 수여한다.
  3. 심판은 특별상을 받지 않은 학생들이 그린 작품 중 자신이 매긴 점수가 가장 높은 $K$개의 작품을 추리고, 그에 해당하는 $K$명의 학생에게 본상을 수여한다.

주최자는 대회에서 종류와 상관 없이 상을 받는 학생들의 작품에 대해 자신이 매긴 점수의 합이 최대가 되도록 하려고 한다. 가능한 합의 최댓값을 구하여라.

입력

첫 번째 줄에 총 학생 수 $N$, 특별상을 수여할 학생의 수 $M$, 본상을 수여할 학생의 수 $K$가 공백으로 구분되어 주어진다. $(2\leq N\leq 2\times 10^5;$ $1\leq M,\ K\leq N-1;$ $M+K\leq N)$

두 번째 줄부터 $N$개의 줄에 걸쳐 각 작품에 대해 주최자가 매긴 점수 $a_i$와 심판이 매긴 점수 $b_i$가 공백으로 구분되어 주어진다. $(0\leq a_i,b_i\leq 10^9)$ 점수는 모두 정수이며, $i\neq j$에 대해 $a_i\neq a_j$, $b_i\neq b_j$를 만족한다.

출력

상을 받는 $M+K$명의 학생이 그린 작품에 대해 주최자가 매긴 점수의 합의 최댓값을 출력한다.

예제 입력 1

7 2 3
4 7
7 8
2 1
9 3
6 0
10 4
3 6

예제 출력 1

33

주최자가 첫 번째와 네 번째 학생을 골라서 특별상을 줄 경우 심판은 자신이 매긴 점수에 따라 두 번째, 여섯 번째, 일곱 번째 학생에게 상을 주게 된다. 이때 상을 받은 $5$명의 작품에 대해 주최자가 매긴 점수의 합은 $33$이 되고, 이것이 가능한 최댓값임을 증명할 수 있다.