Description

There are $n$ schools in country B, each with an ID from $1 \sim n$.

Due to lax administration, it may happen that two schools share the same ID, and some IDs may be unused.

Now the king decides to reassign IDs to all schools so that any two schools have different IDs.

However, changing IDs is a heavy workload, and schools do not want their IDs to change too much. Each school has an acceptable interval for its new ID $[a,b]$, and a unit cost $k$. If a school’s old ID is $m$ and the new ID is $m'$, then the cost to change this school’s ID is $k \times |m'-m|$.

You need to tell the king the minimum total cost to complete the renumbering, or state that it is impossible.

Input Format

The first line contains an integer $n$.

Then follow $n$ lines, each containing four integers $m_i,a_i,b_i,k_i$, meaning that school $i$ has old ID $m_i$, its new ID must be in the range $[a_i,b_i]$, and its unit cost is $k_i$.

Output Format

If there is no assignment such that any two schools have different IDs, output NIE.

Otherwise, output a single integer, the minimum total cost.

5
1 1 2 3
1 1 5 1
3 2 5 5
4 1 5 10
3 3 3 1

9

Hint

Constraints
For $100\%$ of the testdata, $1\le a_i \le m_i \le b_i \le n \le 200$, $1\le k_i \le 1000$.

Translated by ChatGPT 5