题目描述

B 国境内有 n 所学校，每所学校都有一个1∼n 的编号。由于管理过于宽松，可能存在两个学校同时用一个编号的情况，当然也存在一个编号没有学校用的情况。现在国王决定重新给所有学校编号，使得任意两个学校的编号不同。当然，改变编号是一个很繁重的工作，学校不希望自己的编号改变太多。每个学校都有一个可以接受的新编号区间 [a,b]，以及改变编号的单位成本 k。如果一个学校的旧编号为 m，新编号为 m'，那么给这个学校改变编号的成本即为 k×∣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