#P18922. [2026多校联测]金芒山

[2026多校联测]金芒山

金芒山(mango)

题目背景

题目背景

题目描述

有 nn 种芒果,如果种植第 ii 种芒果,会在 i,2i,3i,...i, 2i, 3i, ... 天成熟一次。

现在你有播种机器人,这个机器人有 mm 次操作,每次操作会播种 li,ril_i, r_i 之间全部芒果(可以重复播种,那么同种芒果就会成熟多次)。

现在你能考虑从 1→n1 \to n 的全部天数,你需要为每种芒果分配一个二进制串使得没有一个串是另一个串的前缀,我们称一个分配的权值是每种芒果在 1→n1 \to n 的成熟次数乘上二进制串的长度之和,你希望这个权值尽可能小,输出答案。

输入格式

第一行输入两个整数 n,mn,m。

接下来 mm 行每行输入两个整数 li,ril_i, r_i。

输出格式

输出一行,表示答案。

输入输出样例

样例一

输入
5 2
1 5
1 5
输出
40
解释

第一种芒果会在 1,2,3,4,51,2,3,4,5 每天各成熟两次,总共成熟 1010 次。

第二种芒果会在 2,42,4 每天各成熟两次,总共成熟 44 次。

类似的,我们得到第三四五种会成熟 22 次,我们可以这样分配二进制串:

$$\begin{aligned}1&\to 0,\\2&\to100,\\3&\to101,\\4&\to110,\\5&\to111.\end{aligned}$$

不难发现不存在一个二进制串是另一个串的前缀,总的代价就是:$10 \times 1 + 4 \times 3 + 2 \times 3 + 2 \times 3 + 2 \times 3 = 40$

数据范围

本题采用子任务捆绑,只有通过子任务中的全部测试点才可获得分数。

本题有极大的子任务依赖。

子任务编号 nn mm 特殊性质 分数
11 10210^2 无 1010
22 3×1033 \times 10^3
33 5×1055 \times 10^5 10510^5 2525
44 101010^{10} 11 li=1 ri=nl_i = 1 \ r_i = n 3535
55 10510^5 无 2020