#P17876. Logging Compression
Logging Compression
题目描述
系统中有 类程序,编号为 到 。第 类程序的每个实例启动后,每隔 秒产生一条日志,即相对启动时间的第 秒各产生一条日志。
在时刻 ,系统同时执行 条启动指令。第 条指令为编号在 内的每一类程序分别启动一个实例。不同指令的区间可以重叠;同一类程序可以有多个实例,每个实例独立产生日志。
系统记录时刻 产生的全部日志。每条日志只包含产生它的程序的类别编号。
请为全部 类程序各分配一个非空二进制字符串作为标识符,要求任意一个标识符都不是另一个标识符的前缀。即使某类程序没有产生日志,也需要分配标识符。
一条日志的编码代价等于其所属类别的标识符长度。总编码代价为全部日志的编码代价之和。求最小总编码代价。
输入格式
第一行包含两个整数 ,分别表示程序类别数和启动指令数。
接下来 行,每行包含两个整数 ,表示一条启动指令。
输出格式
输出一个整数,表示最小总编码代价。
样例 1
5 1
1 5
20
样例 2
6 2
1 3
4 6
32
数据范围
- ;
- ;
- 。