Intranational Communications Policy Corporation (ICPC) 聘请你来完成一条新的铁路线，以确保人力和物质资本在整个美国区域内的流动。铁路的路径已经确定，但车站的选址仍有待商榷。这条铁路线将是一条完全的直线，从一个地点出发，途经若干个大都市区，并最终到达另一个地点。每个大都市区都可以用线上的一个点来表示，并对应一个人口数量。ICPC 已经根据沿线的详细人口估算绘制了地图，现在希望选择火车站的位置，以使该线路对人口的效用最大化。

该线路对特定大都市区的效用计算如下：如果该地区的人口为 $p$，则该线路对该人口的价值为 $p \cdot 2^{-d}$，其中 $d$ 是该大都市区沿铁路线到最近火车站的距离。每个大都市区只使用最近的车站，因此其他车站对该地区不产生任何效用。

给定沿规划路线的大都市区人口以及可设置车站数量的上限，确定如何最优地放置这些车站。火车站可以建在沿线的任何位置。

图 K.1：样例输入示意图。大都市区被描绘为线上的点。车站的最优放置位置用红圈标出，距离线路起点分别为 2.0 和 6.0，相应的效用为 $100 + 23 \cdot 1/2 + 28 \cdot 1 + 30 \cdot 1/2 + 10 \cdot 1/4 + 2 \cdot 1/16 = 57.125$。

输入格式

输入的第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $k$ ($1 \le k \le 10^5$)，其中 $n$ 是铁路线上的大都市区数量，$k$ 是可以建造的火车站的最大数量。

接下来的 $n$ 行，每行包含两个整数 $p$ ($1 \le p \le 100$) 和 $d$ ($0 \le d \le 8 \cdot 10^6$)，描述一个大都市区，其中 $p$ 是该大都市区的人口，$d$ 是该大都市区到线路起点的距离。没有两个大都市区会位于距线路起点相同的距离上。为了方便起见，这些区域将按距离的升序给出。

输出格式

输出一个浮点数，表示通过建造最多 $k$ 个火车站，根据上述效用函数所能获得的最大效用。该值必须精确到绝对或相对误差 $10^{-6}$ 以内。

样例

输入 1

6 2
100 2
23 5
28 6
30 7
10 8
2 10

输出 1

157.125