Недавно Иван заметил массив a во время отладки одной программы. Сейчас Иван не может вспомнить этот массив полностью, но ему хотелось бы его восстановить, так как устранить баг до сих пор не получается, но, возможно, тот массив может помочь в устранении.
Иван прекрасно помнит, что в массиве было n элементов, и каждый из них был не меньше 1 и не больше n. Также он помнит q фактов про массив. Существуют два типа фактов, которые помнит Иван:
- 1 li ri vi — для каждого x, такого, что li ≤ x ≤ ri, ax ≥ vi;
- 2 li ri vi — для каждого x, такого, что li ≤ x ≤ ri, ax ≤ vi.
Также Иван считает, что этот массив был перестановкой, но в этом Иван совсем не уверен. Он хочет восстановить такой массив, который бы соответствовал q фактам, в которых Иван точно уверен, и был бы похож на перестановку. Формально, Иван определил стоимость (cost) массива как:
, где cnt(i) равно количеству вхождений i в массив.
Помогите Ивану определить минимально возможную величину cost массива, который бы соответствовал заданным фактам!
Выходные данные
Если факты противоречат друг другу и не существует массива, который бы им соответствовал, выведите -1. Иначе выведите минимально возможное значение величины cost.