CF863F Almost Permutation

Recently Ivan noticed an array $ a $ while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might help him to reproduce the bug. Ivan clearly remembers that there were $ n $ elements in the array, and each element was not less than $ 1 $ and not greater than $ n $ . Also he remembers $ q $ facts about the array. There are two types of facts that Ivan remembers: - $ 1 $ $ l_{i} $ $ r_{i} $ $ v_{i} $ — for each $ x $ such that $ l_{i}

The first line contains two integer numbers $ n $ and $ q $ ( $ 1

If the facts are controversial and there is no array that corresponds to them, print -1. Otherwise, print minimum possible $ cost $ of the array.