Input
20 2
9 19
Output
82
Input
2 1
16 12
Output
-1