Beacon Activation on a Straight Highway

Problem Statement

Beacon Activation on a Straight Highway Problem Description A straight highway has numbered positions 1...m. There are m possible beacons (one per position). If you activate the beacon at position j, it yields a fixed power p_j (possibly 0). You also have n zones along the highway. Zone i covers the inclusive segment [L_i, r_i]. If you choose a subset of beacons to activate, then the benefit of a zone is: 0 if there is no activated beacon inside [L_i, r_i]; otherwise, the power of the activated beacon with the largest position inside [L_i, r_i] (i.e., the rightmost activated beacon inside that zone). Your task: choose which beacons to activate to maximize the sum of benefits over all zones. Input Multiple test cases. First line: Integer t — number of tests (1 ≤ t ≤ 10^5). For each test case: One line with integers n and m (1 ≤ n, m ≤ 10^6). Next n lines: two integers L_i r_i (1 ≤ L_i ≤ r_i ≤ m) — the i-th zone. Next line: m integers p_1, p_2, ..., p_m (0 ≤ p_j ≤ 10^9) — beacon powers.