A2438 | $SZK-Schools$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输出 #1

C++ 编辑器

输入

输出