Reassign School IDs Minimizing Cost

In country B, there are \(n\) schools, each currently having an old ID that is an integer between \(1\) and \(n\). Due to lax management, some IDs may be assigned to more than one school while some IDs may be unused.

The king now wants to reassign new IDs to all schools such that all new IDs are distinct and are chosen from \(1\) to \(n\). However, each school has its own acceptable interval \([a_i, b_i]\) for its new ID, and changing the school\'s ID incurs a cost. If a school\'s old ID was \(m_i\) and its new ID is \(m'_i\), the cost for that school is \(k_i \times |m'_i - m_i|\) where \(k_i\) is a given constant cost factor.

Your task is to determine the minimum total cost required to reassign the IDs while satisfying each school\'s constraints. If it is impossible to assign distinct new IDs in the allowed range for every school, output -1.

Note: An assignment is valid if and only if for each school, the new ID \(m'_i\) satisfies \(a_i \le m'_i \le b_i\) and all new IDs are distinct.

inputFormat

The first line contains a single integer \(n\) (the number of schools).

Then \(n\) lines follow, each containing four integers: \(m_i\), \(a_i\), \(b_i\), and \(k_i\). \(m_i\) is the old ID of the \(i\)-th school, \([a_i, b_i]\) is the acceptable range for the new ID, and \(k_i\) is the cost factor for changing the ID.

It is guaranteed that \(1 \le n \le 500\) (or so) and all numbers are positive integers.

outputFormat

If there exists a valid reassignment, output the minimum total cost. Otherwise, output -1.

sample

3
1 1 3 1
2 1 3 1
3 1 3 1

0