#P17876. Logging Compression

Logging Compression

题目描述

系统中有 nn 类程序,编号为 11 到 nn。第 kk 类程序的每个实例启动后,每隔 kk 秒产生一条日志,即相对启动时间的第 k,2k,3k,…k,2k,3k,\ldots 秒各产生一条日志。

在时刻 00,系统同时执行 mm 条启动指令。第 ii 条指令为编号在 [li,ri][l_i,r_i] 内的每一类程序分别启动一个实例。不同指令的区间可以重叠;同一类程序可以有多个实例,每个实例独立产生日志。

系统记录时刻 1,2,…,n1,2,\ldots,n 产生的全部日志。每条日志只包含产生它的程序的类别编号。

请为全部 nn 类程序各分配一个非空二进制字符串作为标识符,要求任意一个标识符都不是另一个标识符的前缀。即使某类程序没有产生日志,也需要分配标识符。

一条日志的编码代价等于其所属类别的标识符长度。总编码代价为全部日志的编码代价之和。求最小总编码代价。

输入格式

第一行包含两个整数 n,mn,m,分别表示程序类别数和启动指令数。

接下来 mm 行,每行包含两个整数 li,ril_i,r_i,表示一条启动指令。

输出格式

输出一个整数,表示最小总编码代价。

样例 1

5 1
1 5
20

样例 2

6 2
1 3
4 6
32

数据范围

  • 1≤n≤10101\le n\le 10^{10};
  • 1≤m≤1051\le m\le 10^5;
  • 1≤li≤ri≤n1\le l_i\le r_i\le n。