// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define sz(x) int(x.size()) #define pb push_back #define f first #define s second #define mp make_pair using pi = pair<int, int>; template<class T> using V = vector<T>; using vi = V<int>; using vpi = V<pi>; using db = double; const int BIG = 1e8; const db INF = 1e9; const db eps = 1e-5; int main() { cin.tie(0)->sync_with_stdio(0); int N, K; cin >> N >> K; vpi A(N); for(auto& x : A) { cin >> x.s >> x.f; if (x.f == -1) x.f = BIG; } sort(begin(A), end(A)); db ans = INF; for(int x = 0; x <= K; x++) { V<V<db>> dp(x + 1, V<db>(2, INF)), ndp(x + 1, V<db>(2, INF)); // dp[have][ok] dp[0][x == K] = 0; for(int i = 0; i < N; i++) { for(int have = 0; have <= x; have++) for(int ok = 0; ok < 2; ok++) if (dp[have][ok] + eps < INF) { // take i as vote if (have + 1 <= x) { ndp[have + 1][ok] = min(ndp[have + 1][ok], dp[have][ok] + db(A[i].s) / db(K - x + 1)); } // take i as collaborator if (!ok) { if (A[i].f != BIG) { int c = i + 1 - have, nok = c == (K - x); // cout << dp[have][ok] << " " << c << " " << A[i].f << " " << db(A[i].f) / db(c) << endl; ndp[have][nok] = min(ndp[have][nok], dp[have][ok] + db(A[i].f) / db(c)); } } else ndp[have][ok] = min(ndp[have][ok], dp[have][ok]); dp[have][ok] = INF; } dp.swap(ndp); } if (ans < dp[x][1]) break; ans = dp[x][1]; } cout << fixed << setprecision(15); cout << ans << nl; exit(0-0); } // Breathe In, Breathe Out