학교 번호 재배정

어느 나라에 학교가 $n$개 있고, 각 학교는 $1$부터 $n$까지의 번호 $m$을 하나씩 가지고 있습니다. 그런데 지난 통치자가 번호 부여를 제대로 관리하지 않아, 새 학교가 생길 때마다 $1$부터 $n$ 사이의 번호를 자유롭게 고르게 했습니다. 그래서 번호가 서로 다르다는 보장이 없어, 여러 학교가 같은 번호를 쓰기도 하고 $1$부터 $n$ 사이의 어떤 번호는 아예 쓰이지 않기도 합니다. 이상적인 번호 부여란 순열, 즉 $1$부터 $n$까지의 각 번호를 정확히 한 학교에만 배정하는 것입니다.

새 통치자는 모든 번호가 정확히 한 번씩만 쓰이도록 번호 체계를 개편하려 합니다. 하지만 대부분의 학교는 이미 정한 번호를 바꾸기를 꺼립니다.

그래서 각 학교에 어떤 번호까지 받아들일 수 있는지 물었습니다. 학교 $i$는 자기 번호를 그대로 두거나 가까운 번호로만 바꾸고 싶어 하므로, 현재 번호를 포함하는 허용 구간 $[a_i, b_i]$를 제시합니다. 새 번호 $m_i'$는 반드시 $a_i \le m_i' \le b_i$를 만족해야 합니다. 또한 각 학교는 번호를 $1$만큼 바꾸는 데 드는 비용 $k_i$를 밝혔으므로, 학교 $i$의 번호를 $m_i$에서 $m_i'$로 바꾸는 총비용은 $k_i \cdot |m_i - m_i'|$입니다.

모든 학교의 허용 구간을 지키면서 완전한 번호 재배정(순열)이 가능한지, 가능하다면 그 최소 총비용은 얼마인지 구하세요.

첫 줄에 학교의 수 $n$ ($1 \le n \le 200$)이 주어집니다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 네 정수 $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$의 현재 번호, 허용 구간의 왼쪽 끝과 오른쪽 끝(닫힌 구간이므로 새 번호 $m_i'$는 $a_i \le m_i' \le b_i$를 만족해야 함), 그리고 번호를 $1$만큼 바꾸는 데 드는 비용을 뜻합니다.

조건을 만족하는 재배정이 가능하면 그 최소 총비용을 정수 하나로 출력합니다. 불가능하면 (폴란드어로 "아니오"를 뜻하는) NIE를 출력합니다.