铲雪（snow）

有一条宽为 $1$ 米的路。我们将这条路看作一条从 $0$ 开始的数轴。

这条路被划分为 $n$ 段。设 $r_0=0$，第 $i$ 段的范围为第 $r_{i-1}$ 米至第 $r_i$ 米，这一段上雪的厚度均为 $a_i$ 米。

现在有一台推雪车从左向右清理道路，推雪车会将遇到的雪不断向右推动。你可以在路上挖 $k$ 个洞，雪被推到洞的位置时会掉入洞中并消失。

推雪车推动 $1$ 立方米的雪移动 $1$ 米，需要花费 $1$ 元。

你需要确定这 $k$ 个洞的位置（洞的位置可以是实数），使得在清理完所有雪的前提下，最小化总花费。

样例 1 输入

1 2
10 1

样例 1 输出

25.000000000000

样例 1 解释

一种最优方案是在位置 $5$ 和位置 $10$ 挖洞。此时 $[0,5]$ 中的雪被推入位置 $5$ 的洞中，$[5,10]$ 中的雪被推入位置 $10$ 的洞中，总花费为 $25$。

可以证明不存在更优方案。

样例 2

见附加文件中的 snow2.in 和 snow2.ans。

该样例符合测试点 $6$ 的限制。

样例 3

见附加文件中的 snow3.in 和 snow3.ans。

该样例符合测试点 $11$ 的限制。

样例 4

见附加文件中的 snow4.in 和 snow4.ans。

该样例符合测试点 $20$ 的限制。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n$ 行，每行包含两个浮点数 $r_i,a_i$。

输出格式

输出一个浮点数，表示最小花费。

选手输出与标准答案的绝对误差或相对误差不超过 $10^{-4}$ 即视为正确。

提示

对于所有测试数据，保证：

• $1\le n\le 30000$；
• $1\le k\le 50$；
• $0 < a_i \le 10^5$；
• $0=r_0<r_1<r_2<\cdots<r_n \le 10^7$。

输入中的 $r_i,a_i$ 均为浮点数，且小数点后位数不超过 $10$ 位。

• 特殊性质 A：保证 $r_i,a_i$ 均为整数。
• 特殊性质 B：保证所有 $a_i$ 均相等。