This page is still under construction.

Parts of this page are still being built. What you see may change.

Leader-based Team Distribution

Time limit2sMemory limit1024 MB

Summary
Partition N players into M teams of given sizes so the sum of each team's leader player-score (max leader-score member) is maximized.
Level

Medium7 of 10

Topics
Greedy, Sorting, Dynamic programming, Combinatorics
Solved
No attempts yet

Problem

We want to split NN players into MM teams and play a game. The sizes of the teams are t1,t_1, t2,t_2, ⋯ ,\cdots, tMt_M, and player ii has a leader score LiL_i and a player score PiP_i. Each player must belong to exactly one team.

The leader of a team is the player on the team with the largest leader score. If several players on a team tie for the largest leader score, only one of them becomes the leader. The team's ability is defined as the player score of its leader.

Distribute the players among the teams so that the sum of the abilities of all teams is as large as possible.

Input

The first line gives NN and MM. (1≤M≤N≤3⋅1051 \le M \le N \le 3 \cdot 10^5)

The next NN lines each give two integers LiL_i and PiP_i. (1≤Li,Pi≤1051 \le L_i, P_i \le 10^5)

The last line gives MM integers. The ii-th of them is tit_i. (1≤ti≤N1 \le t_i \le N, ∑i=1Mti=N\displaystyle \sum_{i=1}^M t_i = N)

Output

Print the maximum possible sum of the abilities of all teams over all valid distributions of the players.

Examples1

  1. Example 1

    Input
    7 3
    2 4
    2 4
    3 1
    1 2
    3 4
    1 5
    6 7
    1 2 4
    
    Expected output
    16