"""Weighted Interval Scheduling via dynamic programming.

Given intervals (start, end, weight), choose a subset of mutually
non-overlapping intervals maximizing total weight. Intervals overlap when
their time ranges intersect with positive length; touching endpoints
([a,b] and [b,c]) are allowed to coexist.

Algorithm:
  sort intervals by end time
  p[i] = largest index j < i with end_j <= start_i (predecessor)
  OPT[i] = max(OPT[i-1], weight_i + OPT[p[i]])
  answer OPT[n]

Predecessor search uses binary search on sorted end-times: O(n log n).
"""
from __future__ import annotations

import bisect
from typing import List, Tuple


Interval = Tuple[int, int, int]  # (start, end, weight)


def weighted_interval_scheduling(intervals: List[Interval]) -> int:
    """Maximum total weight of a mutually compatible subset.

    Compatibility is the docstring's rule -- an intersection of positive
    length is the only thing that blocks a pair -- so a zero-length
    interval (start == end) overlaps nothing, not even another zero-length
    interval at the same point.  Every zero-length interval with positive
    weight can therefore be taken unconditionally and is added to the
    optimum instead of entering the recurrence, which can only express
    predecessor relations between positive-length ranges.

    A reversed interval (end < start) is not an interval under this rule
    (its range is empty in the other direction) and is rejected rather
    than silently scheduled.
    """
    if not intervals:
        return 0
    free = 0
    admissible: List[Interval] = []
    for s, e, w in intervals:
        if e < s:
            raise ValueError(
                "invalid interval (start %r > end %r): %r" % (s, e, (s, e, w))
            )
        if e == s:
            if w > 0:
                free += w
        else:
            admissible.append((s, e, w))
    if not admissible:
        return free
    # sort by end time; keep original weights
    iv = sorted(admissible, key=lambda x: x[1])
    n = len(iv)
    ends = [iv[i][1] for i in range(n)]
    # dp[i] = best using first i intervals (1-indexed); dp[0]=0
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        s, e, w = iv[i - 1]
        # predecessor: largest j (0..i-1) with ends[j-1] <= s  -> index j in 1-based terms
        # search in ends[0:i-1]
        j = bisect.bisect_right(ends, s, 0, i - 1)  # count of ends <= s among first i-1
        # j is count => predecessor dp index j
        take = w + dp[j]
        skip = dp[i - 1]
        dp[i] = take if take > skip else skip
    return free + dp[n]


def brute_force(intervals: List[Interval]) -> int:
    """Exhaustive enumeration for verification on small inputs.

    Applies the positive-length overlap rule directly and does no input
    validation, so it is only a reference for inputs the scheduler accepts:
    reversed intervals (end < start) are rejected there and are outside
    this function's contract.
    """
    n = len(intervals)
    best = 0
    for mask in range(1 << n):
        chosen = [intervals[k] for k in range(n) if mask & (1 << k)]
        ok = True
        for a in range(len(chosen)):
            for b in range(a + 1, len(chosen)):
                # overlap with positive length
                s1, e1, _ = chosen[a]
                s2, e2, _ = chosen[b]
                lo = max(s1, s2)
                hi = min(e1, e2)
                if hi - lo > 0:
                    ok = False
                    break
            if not ok:
                break
        if ok:
            best = max(best, sum(w for _, _, w in chosen))
    return best


if __name__ == "__main__":
    # self-test with randomized comparison
    import random
    random.seed(42)
    for trial in range(4000):
        n = random.randint(0, 8)
        ivs = []
        for _ in range(n):
            s = random.randint(0, 6)
            length = random.randint(0, 4)  # 0 -> zero-length, admissible
            e = s + length
            w = random.randint(-3, 9)  # signed weights: negatives must be dropped
            ivs.append((s, e, w))
        a = weighted_interval_scheduling(ivs)
        b = brute_force(ivs)
        if a != b:
            raise SystemExit(f"MISMATCH trial={trial} got={a} exp={b} ivs={ivs}")
    print("OK: 4000 randomized trials passed (zero-length and signed weights included)")
    print("example:", weighted_interval_scheduling([(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4)]))