[AdditionalFile5499.zip](file://AdditionalFile5499.zip?type=additional_file)

#5499. 「POI2006 R2」学校 Schools

标签: 传统 | 时间限制: 100 ms | 内存限制: 32 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – II etap Szkoły

在字节国（Bajtocja），有 $n$ 所学校，每所学校都被分配了一个编号 $m$，其中 $1 \le m \le n$。字节国的前任国王完全不关心学校编号的秩序，允许每所新建的学校从 $1$ 到 $n$ 的范围内任意选择一个编号。因此，国内可能出现了多所学校使用相同编号的情况，而某些从 $1$ 到 $n$ 的编号可能根本未被使用。

字节国的新国王决定恢复秩序，对学校进行重新编号，使得每个编号都恰好被使用一次。然而，这并非一项简单的任务，因为大多数学校都不愿意更改自己的编号。

国王派遣了他的信息员前往各个学校，以了解每所学校能接受多大程度的编号变更。此外，每所学校都为其编号每变更 $1$ 个单位的成本设定了一个值 $c$。因此，更改某所学校编号的总成本为 $c \cdot |m - m'|$，其中 $m$ 代表该校的旧编号，$m'$ 代表新编号。当然，新编号 $m'$ 必须在该校先前给出的容忍范围内。

国王在收到上述信息后，想知道是否有可能在遵守所有学校容忍范围的前提下恢复学校编号的秩序。如果可能，那么完成这种重新编号的最低成本是多少。因此，他请求你这个他的宫廷计算机科学家根据他提供的学校数据，给出这些信息。

请编写一个程序，实现以下功能：

• 从标准输入读取字节国各学校的当前编号、它们对于编号变更的容忍范围以及将各自编号变更 $1$ 的成本，
• 检查是否存在一种满足前述所有条件的学校重新编号方案，如果存在，则计算出这种变更的最低成本，
• 将结果输出到标准输出。

输入格式

输入的第一行包含一个整数 $n$ $(1 \le n \le 200)$，表示字节国的学校数量。

接下来的 $n$ 行包含各个学校的描述。第 $i+1$ $(1 \le i \le n)$ 行包含四个整数 $m_i, a_i, b_i, k_i$ $(1 \le a_i \le m_i \le b_i \le n, 1 \le k_i \le 1000)$，由单个空格隔开。这些数字分别表示：第 $i$ 所学校的当前编号、第 $i$ 所学校关于编号变更的容忍范围的起始和结束（这是一个闭区间，即第 $i$ 所学校的新编号 $m_i'$ 必须满足不等式 $a_i \le m_i' \le b_i$），以及将第 $i$ 所学校的编号变更 $1$ 的成本。

输出格式

如果满足上述条件的学校重新编号是可能的，程序应输出一个整数 $k$，表示重新编号的最低可能成本。否则，应输出 NIE。

样例

输入

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

输出

9