Festival Coverage

Festival Coverage

Time limit: 2 s.
Memory limit: 256 MB

During a major festival in Saudi Arabia, Fares and Abdulaziz are organizing services along a very long road.

There are several service teams, and each team becomes available at a certain time. Once a team becomes available, it can serve everyone located inside its assigned interval on the road.

There are also important target locations on the road that must all be served.

For each team, you are given:

  • the time when it becomes active;
  • the left endpoint of the interval it covers;
  • the right endpoint of the interval it covers.

A target point \(x\) is covered by an interval \([l_i, r_i]\) if \(l_i \le x \le r_i\). In particular, the endpoints are included.

Your task is to find the earliest time such that every target location is covered by at least one active interval.

If it is impossible for all target locations to be covered, print \(-1\).

Input

The first line contains two integers \(n\) and \(m\) — the number of intervals and the number of target points.

Each of the next \(n\) lines contains three integers \(t_i\), \(l_i\), and \(r_i\) — the activation time of the interval, and its left and right endpoints.

The last line contains \(m\) integers \(x_1, x_2, \ldots, x_m\) — the target points.

It is guaranteed that:

  • \(1 \le n, m \le 2 \cdot 10^5\);
  • \(1 \le t_i \le 10^9\);
  • \(-10^9 \le l_i \lt r_i \le 10^9\);
  • \(-10^9 \le x_i \le 10^9\).

Output

Print a single integer: the minimum time when all target points are covered.

If it is impossible to cover all target points, print \(-1\).

Scoring

Subtask Additional constraints Points
\(1\) \(1 \le n, m \le 200\) \(14\)
\(2\) all intervals become active at the same time \(13\)
\(3\) the target points are exactly \(1, 2, \ldots, m\), and \(1 \le n, m \le 5000\) \(11\)
\(4\) the target points are exactly \(1, 2, \ldots, m\) \(13\)
\(5\) no two intervals overlap at all, and \(1 \le n, m \le 5000\) \(17\)
\(6\) no two intervals overlap at all \(15\)
\(7\) no additional constraints \(17\)

Examples

Input

4 5
3 1 4
1 6 8
5 2 7
2 9 10
2 3 6 7 10

Output

3

Input

3 4
2 1 3
5 6 8
7 10 12
2 4 7 11

Output

-1

Note

Notes for Sample 1:

At time \(T\), an interval is active if \(t_i \le T\).

A target point \(x\) is covered if it lies inside at least one active interval, that is, if there exists an active interval \([l_i, r_i]\) such that \(l_i \le x \le r_i\).

In Sample 1, the target points are \(2, 3, 6, 7, 10\).

  • At time \(1\), only the interval \([6, 8]\) is active.
    • Point \(2\) is not covered.
    • Point \(3\) is not covered.
    • Point \(6\) is covered by \([6, 8]\).
    • Point \(7\) is covered by \([6, 8]\).
    • Point \(10\) is not covered.
  • At time \(2\), the intervals \([6, 8]\) and \([9, 10]\) are active.
    • Point \(2\) is not covered.
    • Point \(3\) is not covered.
    • Point \(6\) is covered by \([6, 8]\).
    • Point \(7\) is covered by \([6, 8]\).
    • Point \(10\) is covered by \([9, 10]\).
  • At time \(3\), the intervals \([1, 4]\), \([6, 8]\), and \([9, 10]\) are active.
    • Point \(2\) is covered by \([1, 4]\).
    • Point \(3\) is covered by \([1, 4]\).
    • Point \(6\) is covered by \([6, 8]\).
    • Point \(7\) is covered by \([6, 8]\).
    • Point \(10\) is covered by \([9, 10]\).

Therefore, the answer for Sample 1 is \(3\).

Notes for Sample 2:

At time \(T\), an interval is active if \(t_i \le T\).

A target point \(x\) is covered if it lies inside at least one active interval, that is, if there exists an active interval \([l_i, r_i]\) such that \(l_i \le x \le r_i\).

In Sample 2, the target points are \(2, 4, 7, 11\).

  • At time \(2\), only the interval \([1, 3]\) is active.
    • Point \(2\) is covered by \([1, 3]\).
    • Point \(4\) is not covered.
    • Point \(7\) is not covered.
    • Point \(11\) is not covered.
  • At time \(5\), the intervals \([1, 3]\) and \([6, 8]\) are active.
    • Point \(2\) is covered by \([1, 3]\).
    • Point \(4\) is still not covered.
    • Point \(7\) is covered by \([6, 8]\).
    • Point \(11\) is not covered.
  • At time \(7\), the intervals \([1, 3]\), \([6, 8]\), and \([10, 12]\) are active.
    • Point \(2\) is covered by \([1, 3]\).
    • Point \(4\) is still not covered.
    • Point \(7\) is covered by \([6, 8]\).
    • Point \(11\) is covered by \([10, 12]\).

Point \(4\) is never covered by any interval, so there is no time when all target points are covered.

Therefore, the answer for Sample 2 is \(-1\).

Note that intervals may overlap, and target points may repeat.

Solution

For a target point \(x\), we need the smallest activation time among all intervals containing \(x\). The answer is the maximum of these earliest times over all target points.

Sort intervals by their left endpoint and target points by position. Sweep from left to right. Before processing \(x\), add every interval with \(l_i\le x\) to a priority queue ordered by activation time. Remove intervals from the top while their right endpoint is smaller than \(x\). The top is then the earliest active interval covering \(x\).

If the queue becomes empty, that target can never be covered.

The complexity is \(O((N+M)\log N)\) time and \(O(N+M)\) memory.

#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

struct Interval {
    long long time;
    long long left;
    long long right;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Interval> intervals(n);
    for (Interval& interval : intervals) {
        cin >> interval.time >> interval.left >> interval.right;
    }

    vector<long long> targets(m);
    for (long long& x : targets) {
        cin >> x;
    }

    sort(intervals.begin(), intervals.end(),
        [](const Interval& a, const Interval& b) {
            return a.left < b.left;
        });
    sort(targets.begin(), targets.end());

    priority_queue<
        pair<long long, long long>,
        vector<pair<long long, long long>>,
        greater<pair<long long, long long>>
    > active;

    int nextInterval = 0;
    long long answer = 0;

    for (long long x : targets) {
        while (nextInterval < n && intervals[nextInterval].left <= x) {
            active.push( {
                intervals[nextInterval].time,
                intervals[nextInterval].right
            });
            nextInterval++;
        }

        while (!active.empty() && active.top().second < x) {
            active.pop();
        }

        if (active.empty()) {
            cout << -1 << '\n';
            return 0;
        }

        answer = max(answer, active.top().first);
    }

    cout << answer << '\n';
}