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 is one possible beacon at every position. Activating the beacon at position j makes that beacon emit a fixed power p_j (possibly 0 ). There are also n zones along the highway. Zone i covers the inclusive segment [L_i, r_i] . Once you have chosen a subset of beacons to activate, the benefit of zone i is: 0 , if no activated beacon lies inside [L_i, r_i] ; otherwise, the power of the activated beacon at the largest position inside [L_i, r_i] — that is, the rightmost activated beacon inside that zone. Note that a zone is served by its rightmost activated beacon, not by its strongest one, so activating an extra beacon can reduce the total. Choose which beacons to activate so that the sum of the benefits of all n zones is as large as possible, and report that sum. Input The input contains multiple test cases. The first line contains one integer t — the number of test cases. Ea