Byteotia 有 $n$ 所学校，每所学校都有一个编号 $m$（$1 \le m \le n$）。然而，Byteotia 的前任国王对学校编号并不在意，慷慨地允许每所新学校在 $1 \dots n$ 的范围内任意选择编号。因此，无法保证编号是唯一的，事实上这种情况极不可能发生。显然，一些学校可能选择了相同的编号，导致 $1 \dots n$ 范围内的一些数字根本没有被使用。完美的编号方案应该是一个排列，即该范围内的每个数字都恰好分配给一所学校。

新加冕的 Byteotia 国王想要改革编号系统，使得每个数字都被恰好使用一次。但这并非易事，因为大多数学校都不愿意更改它们已经选择的编号。

国王派遣了他最信任的线人前往所有学校，询问每所学校愿意接受哪些编号。由于每所学校都希望保留其当前的编号（或者至少是接近它的编号），每位校长都指定了一个包含该校当前编号的区间，这些区间被称为容忍区间。此外，每所学校还说明了将其编号更改 $1$ 个单位所需的成本 $c$。因此，更改一所学校编号的总成本等于 $c \cdot |m - m'|$，其中 $m$ 表示旧编号，$m'$ 表示新编号。当然，$m'$ 必须位于该校指定的容忍区间内。

现在，收集了所有信息后，国王想知道是否有可能引入一种完美的编号方案（同时遵守每所学校的容忍区间），如果可以，这种重新编号的最小成本是多少。他请求你——皇家计算机科学家——仔细研究他提供的信息并给出答案。

编写一个程序，完成以下任务：

• 从标准输入读取 Byteotia 各学校的当前编号、它们的容忍区间以及更改编号的单位成本。
• 检查是否可以在满足所有上述条件的情况下对学校进行完美重新编号，如果可以，确定重新编号的最小成本。
• 将结果写入标准输出。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 200$），表示 Byteotia 的学校数量。接下来的 $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 1\,000$），用空格分隔。它们分别表示：第 $i$ 所学校的当前编号、该校编号容忍区间的左端点和右端点（这是一个闭区间，因此第 $i$ 所学校的新编号 $m_i'$ 必须满足不等式 $a_i \le m_i' \le b_i$），以及更改第 $i$ 所学校编号 $1$ 个单位的成本。

输出格式

如果可以实现满足上述条件的重新编号，程序应输出一个整数 $k$，表示执行该操作的最小成本。如果无法实现，则输出单词 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