Customer satisfaction
Binary search
Algorithms
71.0% success
8,758 attempts
2s time
256MB memory
1024KB max code

Alice is the biggest seller in the town who sells notebooks. She has $$N$$ customers to satisfy. Each customer has three parameters $$L_i$$, $$R_i$$, and $$Z_i$$ denoting the arrival time, departure time, and quantity of notebooks required.

Each customer has to be supplied a total of $$Z_i$$ notebooks between $$L_i$$ and $$R_i$$ inclusive. What is the minimum rate of $$W$$ notebooks per unit time by which if Alice produces so that it satisfies the demand of each customer?

Note that Alice does not need to supply $$Z_i$$ to customer $$i$$ for per unit time but the total of $$Z_i$$ between $$L_i$$ and $$R_i$$ and distribution does not need to be uniform.

Input format

  • The first line contains \(T\) denoting the number of test cases.
  • The first line of each test case contains an integer $$N$$.
  • Next $$N$$ lines of each test case contains three space-seperated integers $$L_i$$, $$R_i$$, and $$Z_i$$ as described in the problem statement,

Output format

For each test case, print a single line containing the minimum rate of production $$W$$.

Constraints

\(1 \leq T \leq 1000\)

\(1 \leq N \leq 200000\)

\(1 \leq L[i],R[i],Z[i] \leq 200000 \forall i \in [1,N]\)

\(L[i] \leq R[i] \forall i \in [1,N]\)

\(\sum_{i=1}^{T} N \leq 200000\)

Examples
Input
1
3
2 2 1
2 3 3
2 3 1
Output
2
Explanation

For W=2,

for t=2 we alice will produce 4 notebooks so he will satisfy 1st and 2nd customer leading now he has 0 notebooks and t=3 he will have 2 notebooks which he has produced during t=2 and t=3 and satisfy customer 3.

For W=1 he will be unable to satisfy all three.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...