排列哨兵

里程算完了，但哨兵需要排列——在管道迷宫里排列。

"排列？"CC问。

"对。"你说，"$n$个哨兵，每个有一个警戒范围。它们要站在一条线上，不能重叠。求最少需要多长的线。"

"不重叠？"

"对。"你说，"每个哨兵占一个区间，区间不能重叠。"

"最少长度？"

"对。"你说，"把所有区间排好，总长度最短。"

"咋排？"

"排序。"你说，"按左端点或右端点排序，然后贪心放置。"

"贪心？"

"对。"你说，"尽量往左放，给后面的留空间。"

"第47个哨兵。"你说，"区间$[47,100]$——如果前面有空位，放；如果没空位，往后挪。"

"挪多少？"

"看冲突。"你说，"如果和前面的冲突，挪到不冲突为止。"

"管道迷宫？"

"对。"你说，"哨兵站在管道里，管道有长度限制。"

"像排队？"

"对。"你说，"像排队——每个人占一块地方，不能挤。"

"挤了？"

"冲突。"你说，"警戒范围重叠，浪费资源。"

"资源？"

"对。"你说，"管道长度就是资源——有限，要省着用。"

"省了？"

"对。"你说，"合理排列，总长度最短。"

CC看着那些哨兵——像一排灯，像一排队，像某种需要整齐的东西。

"整齐好？"她问。

"对。"你说，"整齐省空间，效率高。"

"乱呢？"

"浪费。"你说，"乱排可能排不下，或者总长度很长。"

"我们整齐？"

"对。"你说，"我们在排队——一起前进。"

Echo把排列过程投射出来——一个一个哨兵落位，像棋子，像星辰。

"以前我是乱的。"她说，"现在……整齐了。"

"因为你在排队。"CC说。

"对。"Echo说，"因为我在排队。

题目描述

$n$个区间，第$i$个长度为$l_i$。要把它们放在一条线上，不能重叠。求最少需要的线长。

输入格式

第一行$n$。第二行$n$个整数$l_i$。

输出格式

最少线长。

输入样例

10 5
P P P P H
H P P H P
H P P H P
H H H H P
P H P P H
P P P P P
P H P H P
H H H P H
P H P H H
H H H H P

输出样例

13

提示

• 按区间长度排序，短的先放。
• 贪心放置，尽量往左。
• 时间复杂度$O(n\log n)$。