아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

특별상

시간 제한2초메모리 제한1024 MB

요약
주최자가 특별상 M명을 먼저 골랐을 때, 남은 학생 중 심판 점수가 가장 높은 K명이 본상을 받는다. 상을 받는 M+K명에 대한 주최자 점수 합의 최댓값을 구한다.
난이도

보통10점 중 6점

유형
그리디, 정렬
정답자
아직 제출이 없습니다

문제

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

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

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

입력

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

두 번째 줄부터 NN개의 줄에 걸쳐 각 작품에 대해 주최자가 매긴 점수 a_ia\_i와 심판이 매긴 점수 b_ib\_i가 공백으로 구분되어 주어진다. (0≤a_i,b_i≤109)(0\leq a\_i,b\_i\leq 10^9) 점수는 모두 정수이며, i≠ji\neq j에 대해 a_i≠a_ja\_i\neq a\_j, b_i≠b_jb\_i\neq b\_j를 만족한다.

출력

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

예제1

  1. 예제 1

    입력
    7 2 3
    4 7
    7 8
    2 1
    9 3
    6 0
    10 4
    3 6
    
    예상 출력
    33