Lantern Leasing

# Lantern Leasing ## Problem Farmer John is leasing lanterns to brighten the barns at his farm. He has a row of $N$ stalls, numbered $1$ to $N$. Initially, all stalls have brightness $0$. He receives $M$ lantern rental requests. Each request specifies a contiguous range of stalls and the brightness level that lantern provides. When a lantern is rented, it adds its brightness to all stalls in its range. After all lanterns are rented, determine: 1. The maximum brightness level achieved by any stall 2. How many stalls have exactly this maximum brightness level ## Input The first line contains two integers $N$ and $M$ ($1 \le N, M \le 10^5$). The next $M$ lines each contain three integers $l$, $r$, and $b$ ($1 \le l \le r \le N$, $1 \le b \le 10^3$), indicating that a lantern adds brightness $b$ to all stalls from $l$ to $r$ inclusive. ## Output Output two integers on a single line: - The maximum brightness among all stalls - The number of stalls that have this maximum brightness ## Constraints - $1 \le N, M \le 10^5$ - $1 \le b \le 10^3$ - Stalls are numbered from $1$ to $N$ ## Sample ### Input ``` 6 3 1 3 2 2 5 1 4 6 3 ``` ### Output ``` 4 2 ``` ### Explanation We have 6 stalls. Starting with brightness $[0, 0, 0, 0, 0, 0]$: - Lantern 1 adds brightness 2 to stalls 1-3: $[2, 2, 2, 0, 0, 0]$ - Lantern 2 adds brightness 1 to stalls 2-5: $[2, 3, 3, 1, 1, 0]$ - Lantern 3 adds brightness 3 to stalls 4-6: $[2, 3, 3, 4, 4, 3]$ The maximum brightness is 4, achieved at exactly 2 stalls (stalls 4 and 5).