Un sistema contiene $n$ tipos de programas, numerados del $1$ al $n$. Una vez que se inicia una instancia de un programa de tipo $k$, genera una entrada de registro cada $k$ segundos; concretamente, en los instantes $k,2k,3k,\ldots$ relativos a su instante de inicio.
En el instante $0$, el sistema ejecuta $m$ órdenes simultáneamente: la $i$-ésima orden inicia una instancia de cada tipo de programa cuyo índice pertenece al intervalo $[l_i,r_i]$. Ten en cuenta que, si los intervalos de varias órdenes se solapan, pueden iniciarse varias instancias del mismo tipo de programa, y cada instancia genera registros de forma independiente.
El sistema guarda todas las entradas de registro generadas en los instantes $1,2,\ldots,n$. Cada registro contiene únicamente el índice del tipo de programa correspondiente a la instancia que lo generó.
Tu tarea consiste en diseñar un algoritmo para comprimir estos registros: debes asignar una cadena binaria no vacía como identificador a cada uno de los $n$ tipos de programas, garantizando que ningún identificador sea prefijo de otro. El coste de codificar un registro es la longitud del identificador asignado al tipo de programa correspondiente, y el coste total es la suma de los costes de todos los registros. Encuentra el mínimo coste total posible.
Entrada
La primera línea contiene dos enteros $n,m$ ($1\le n\le10^{10}$, $1\le m\le10^5$), que representan el número de tipos de programas y el número de órdenes.
Cada una de las siguientes $m$ líneas contiene dos enteros $l_i,r_i$ ($1\le l_i\le r_i\le n$), que representan una orden de inicio.
Salida
Imprime un único entero: el mínimo coste total.
Ejemplos
Entrada 1
5 1 1 5
Salida 1
20
Entrada 2
6 2 1 3 4 6
Salida 2
32
Nota
Supón que los registros se guardan en orden cronológico; para los registros generados en el mismo instante, se sigue un orden monótono no decreciente según el índice del tipo de programa correspondiente.
En el primer ejemplo, los registros son $[1,1,2,1,3,1,2,4,1,5]$. Una asignación óptima de identificadores es (programa $1$: 0, programa $2$: 100, programa $3$: 101, programa $4$: 110, programa $5$: 111). El coste es $5\times1+2\times3+1\times3+1\times3+1\times3=20$.
En el segundo ejemplo, los registros son $[1,1,2,1,3,1,2,4,1,5,1,2,3,6]$. Una asignación óptima de identificadores es (programa $1$: 0, programa $2$: 10, programa $3$: 1100, programa $4$: 1101, programa $5$: 1110, programa $6$: 1111). El coste es $6\times1+3\times2+2\times4+1\times4+1\times4+1\times4=32$.