[POI2006] SZK-Schools
题目描述
B 国境内有 $n$ 所学校,每所学校都有一个 $1 \sim n$ 的编号。
由于管理过于宽松,可能存在两个学校同时用一个编号的情况,当然也存在一个编号没有学校用的情况。
现在国王决定重新给所有学校编号,使得任意两个学校的编号不同。
当然,改变编号是一个很繁重的工作,学校不希望自己的编号改变太多。每个学校都有一个可以接受的新编号区间 $[a,b]$,以及改变编号的单位成本 $k$。如果一个学校的旧编号为 $m$,新编号为 $m'$,那么给这个学校改变编号的成本即为 $k \times |m'-m|$。
现在你需要告诉国王完成编号更新的最低成本是多少,或者说明这是不可能的。
输入输出格式
输入格式
第一行一个整数 $n$。
接下来 $n$ 行,每行四个整数 $m_i,a_i,b_i,k_i$,代表 $i$ 号学校的旧编号为 $m_i$,新编号的范围为 $[a_i,b_i]$,改变编号的单位成本为 $k_i$。
输出格式
如果不存在一种方案,使得任意两个学校的编号不同,输出 `NIE`。
否则输出一个整数,代表最小成本。
输入输出样例
输入样例 #1
5
1 1 2 3
1 1 5 1
3 2 5 5
4 1 5 10
3 3 3 1
输出样例 #1
9
说明
【数据范围】
对于 $100\%$ 的数据,$1\le a_i \le m_i \le b_i \le n \le 200$,$1\le k_i \le 1000$。