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

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

리더 기반 팀 분배

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

요약
N명의 선수를 정해진 크기의 M개 팀으로 나눌 때, 각 팀에서 리더 점수가 가장 높은 선수의 플레이어 점수 합을 최대로 만든다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 동적 계획법, 조합론
정답자
아직 제출이 없습니다

문제

플레이어 NN명을 MM개의 팀으로 나누어 게임을 진행하려 한다. 각 팀의 인원수는 t1,t_1, t2,t_2, ⋯ ,\cdots, tMt_M이고, ii번째 플레이어는 리더 점수 LiL_i와 플레이어 점수 PiP_i를 가진다. 각 플레이어는 정확히 한 팀에 속해야 한다.

각 팀의 리더는 팀에 속한 플레이어 중 리더 점수가 가장 큰 사람이다. 한 팀에서 리더 점수가 가장 큰 플레이어가 여러 명이면 그중 한 명만 리더가 된다. 팀의 능력은 리더의 플레이어 점수로 정의한다.

플레이어를 각 팀에 적절히 분배해 모든 팀의 능력 합을 최대한 크게 만들어 보자.

입력

첫째 줄에 NN, MM이 주어진다. (1≤M≤N≤3⋅1051 \le M \le N \le 3 \cdot 10^5)

이어지는 NN개의 줄에 걸쳐 두 정수 LiL_i와 PiP_i가 주어진다. (1≤Li,Pi≤1051 \le L_i, P_i \le 10^5)

마지막 줄에는 MM개의 정수가 주어진다. ii번째 수는 tit_i이다. (1≤ti≤N1 \le t_i \le N, ∑i=1Mti=N\displaystyle \sum_{i=1}^M t_i = N)

출력

플레이어를 각 팀에 적절히 분배했을 때 모든 팀의 능력 합의 최댓값을 출력한다.

예제1

  1. 예제 1

    입력
    7 3
    2 4
    2 4
    3 1
    1 2
    3 4
    1 5
    6 7
    1 2 4
    
    예상 출력
    16