\problemname{Train Line}

The Iowa Communications Policy Corporation (ICPC) has hired you to complete a new rail line to ensure flow of human and physical capital across a sector of the state. The path of the railway has already been decided, but where to place the stations is still up for debate. The rail line will be a completely straight line starting at one location, traveling through a number of metropolitan areas, and ending at another location. Each metropolitan area can be represented by a single point on the line with a corresponding population. The ICPC has made the map very detailed in its estimate of the population along the line and now wants to pick placement of rail stations so as to maximize the utility of the line to the population.

The utility of the line to a particular metropolitan area can be determined as follows. If the area has population $p$, the value of the line to that population is $p \cdot 2^{-d}$, where $d$ is the distance of the metropolitan area along the line to the nearest rail station. Because funds are tight, the number of rail stations the ICPC would like built is extremely limited. Your job is to determine how to build these stations optimally.

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=.7\textwidth]{sample-line.png}
	\end{center}
	\caption{Illustration of sample input. Metropolitan areas are depicted as points on the line. The optimal placement of stations is given in red circles, at distance $2.0$ and $6.0$ from the start of the line, with respective utility $100$ and $23 \cdot 1/2 + 28 \cdot 1 + 30 \cdot 1/2 + 10 \cdot 1/4 + 2 \cdot 1/16 = 57.125$.}
	\label{fig:sample}
\end{figure}

\section*{Input}

Input will begin with a line consisting of two integers $n$ ($1 \leq n \leq 30\,000$), the number of metropolitan areas on the train line, and $k$ ($1 \leq k \leq 6$), the maximum number of rail stations that may be constructed. The next $n$ lines each describe a metropolitan area. Each line will consist of two integers $p_i$ ($1 \leq p_i \leq 100$), the population of the given metropolitan area, and $d_i$ ($0 \leq d_i \leq 8\,000\,000$), the distance of the metropolitan area to the start of the line. No two metropolitan areas will be located at the same distance from the start of the line. For your convenience, the areas will be given in sorted order by distance, so $d_i < d_{i+1}$.

\section*{Output}

Output the maximum utility possible by constructing at most $k$ rail stations, according to the above utility function. Rail stations can be built at any position along the line. ICPC only cares about the digits before the decimal place, so your answer will be considered correct if it is within an integer of the exact answer.
