Schools

Memory limit: 32 MB

There are schools in Byteotia, and each has its number , , just as every school tends to. However, the previous king of Byteotia paid little attention to the school numbering, and generously allowed every new school to choose any number from the range - . There is thus no guarantee that the numbers are unique, in fact it seems highly unlikely. Clearly some schools may have chosen the same number, and as a consequence some numbers from the range - might be not used at all. A perfect numbering would be a permutation, i.e. a one that assigns each number from the specified range to exactly one school.

The newly crowned king of Byteotia wants to reform the numbering system, so that every number would be used exactly once. It is, however, not an easy task, since most schools are reluctant to change the numbers they have once chosen.

The king has sent his most trusted informants to all the schools to inquire which numbers each school would accept. Since every school would like to keep its current number (or at least a number close to it), each school director has specified an interval containing the school's current number. These intervals are called the tolerance intervals. Furthermore, each school has stated the cost of changing its number by . Hence the total cost of changing a school's number equals , where denotes the old school number, and the new one. Of course must lie in the tolerance interval previously specified by the school.

Now, all the information gathered, the king would like to know, if it's possible to introduce a perfect numbering (while complying with every school's tolerance interval), and if so, what is the minimal cost of such reenumaration. He has asked you - the royal computer scientist - to carefully study the information he has provided you with and give the answer in return.

Task

Write a programme that:

• reads from the standard input the current numbers of Byteotian schools, their tolerance intervals and the costs of changing their numbers by ,
• checks if it's possible to perfectly reenumerate the schools complying with all previously described conditions, and if so, determines the minimal cost of such reenumeration,
• writes the result to the standard output.

Input

The first line of the standard input contains one integer (), denoting the number of schools in Byteotia. In the following lines there are descriptions of the schools themselves. The line no. () contains four integers , , and (, ), separated by single spaces. These denote respectively: the current number of the -th school, the left and right endpoint of the -th school's tolerance interval regarding the change of number (it is a closed interval, therefore the new -th school's number must satisfy the inequality ) and the cost of changing the number of -th school by .

Output

If a reenumeration satisfying the above conditions is possible, the programme should write one integer denoting the minimum possible cost of performing the operation. If it's not possible, it should write the word NIE, which means NO in Polish.

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

9

Print friendly version