K Best

Time limit2sMemory limit64 MB

Summary

Choose exactly k jewels out of n to maximize the ratio of total value to total weight, using binary search on the answer with a fractional feasibility check, then output the exact reduced fraction.

Level: Medium7 of 10
Topics: Binary search, Greedy, Math
Solved: No attempts yet

Problem

Demy has $n$ jewels. The $i$ -th jewel has value $v_i$ and weight $w_i$ .

She wants to keep exactly $k$ of them so that their specific value is as large as possible. For a chosen set $S = \{i_1, i_2, \ldots, i_k\}$ the specific value is defined as

$s(S) = \frac{\sum_{j=1}^{k} v_{i_j}}{\sum_{j=1}^{k} w_{i_j}}.$

Determine the maximum possible specific value over all subsets of size $k$ .

Input

The first line contains two integers $n$ and $k$ — the number of jewels and the number to keep ( $1 \le k \le n \le 100\,000$ ).

Each of the next $n$ lines contains two integers $v_i$ and $w_i$ ( $0 \le v_i \le 10^6$ , $1 \le w_i \le 10^6$ ). Both $\sum v_i$ and $\sum w_i$ are at most $10^7$ .

Output

The maximum specific value is a rational number. Output it as an irreducible fraction p/q, where $p \ge 0$ and $q \ge 1$ are integers with $\gcd(p, q) = 1$ . Always print the denominator (for example 3/1). If the value is $0$ , print 0/1.

Examples4

Example 1
Input
```
3 2
1 1
1 2
1 3
```
Expected output
```
2/3
```
Example 2
Input
```
1 1
5 2
```
Expected output
```
5/2
```
Example 3
Input
```
3 1
1 2
3 1
2 5
```
Expected output
```
3/1
```
Example 4
Input
```
4 4
1 1
2 2
3 3
4 4
```
Expected output
```
1/1
```