#include <iostream>
#include <cmath>

using namespace std;

constexpr int MAXN = 3e4 + 4;
constexpr int CHEESE = 20;
int p[MAXN], d[MAXN];

int old = 0;
double dp[2][MAXN];

double eval(int l, int r, double c) {
    // note that the distance function causes contributions to fall off extremely quickly
    // thus to cheese, we look at a small window around the queried point
    int idx = lower_bound(p + l, p + r + 1, static_cast<int>(c)) - p;

    double ans = 0.0;
    for (int i = max(l, idx - CHEESE); i <= min(idx + CHEESE, r); ++i) {
        ans += p[i] * pow(2.0, -abs(d[i] - c));
    }

    return ans;
}

double C(int l, int r) {
    // cost of covering [l, r]
    double lo = d[l];
    double hi = d[r];

    double f1, f2;
    for (int iter = 0; iter < 50; ++iter) {
        double dist = (hi - lo) / 3.0;
        double m1 = lo + dist;
        double m2 = hi - dist;

        f1 = eval(l, r, m1);
        f2 = eval(l, r, m2);

        if (f1 < f2) {
            lo = m1;
        } else {
            hi = m2;
        }
    }

    return (f1 + f2) / 2.0;
}

// Is this even right? idk
void compute(int l, int r, int optl, int optr) {
    if (l > r) {
        return;
    }

    int mid = (l + r) / 2;
    pair<double, int> best = {0.0, -1};
    for (int k = optl; k <= min(mid, optr); ++k) {
        best = max(best, {dp[old][k - 1] + C(k, mid), k});
    }

    dp[old ^ 1][mid] = best.first;
    int opt = best.second;

    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

int main() {
    int n, k;
    scanf(" %d %d", &n, &k);

    for (int i = 1; i <= n; ++i) {
        scanf(" %d %d", &p[i], &d[i]);
    }

    for (int i = 1; i <= k; ++i, old ^= 1) {
        compute(1, n, 1, n);
    }

    cout << dp[old][n] << '\n';

    return 0;
}
