<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

366. Computer Game
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



BerSoft company recently released new computer game, where you play against N opponents. During the game you need to tell to K opponents your opinion about them. You feel pleasure after that and get several score points after that. Each opponent described by two parameters ai and bi, where ai is the amount of pleasure you get when you tell your opinion about this opponent; bi amount of score points you get in that case. Let us denote A and B summary pleasure and score points that you get during the game. You have never played this game; therefore you don't know what is now what is more advantageous: get more pleasure or score points. You decided to make these values as close as possible. Your task is to select K opponents in a way that minimizes |A - B|. If there are several ways to do it, choose one that maximizes A + B.

Input
The first line of the input file contains integer number N, K (1 ≤ N ≤ 60000; 1 ≤ K ≤ min(N, 20)). Next N lines contain two integer numbers each — i-th opponent parameters ai and bi (0 ≤ ai ≤ 50; 0 ≤ bi ≤ 50).

Output
On the first line of the output file print values A and B. Print numbers of K selected opponents on the second line. Print numbers in ascending order. If there are several solutions, output any of them.

Example(s)
sample input
sample output
4 2
1 2
2 3
4 1
6 2
6 4
2 3

sample input
sample output
5 3
13 11
3 17
15 20
6 13
17 9
36 33
1 4 5

<|response|>
## 1) Abridged problem statement (concise)

You have **N** opponents (up to 60000). Opponent *i* gives you two values \((a_i, b_i)\) (both in \([0, 50]\)).
Choose **exactly K** opponents (\(K \le 20\)) so that:

1) \(|A - B|\) is minimized, where \(A=\sum a_i\), \(B=\sum b_i\) over chosen opponents.
2) If multiple choices minimize \(|A-B|\), pick one with maximum \(A+B\).

Output \(A\), \(B\), and the chosen indices (ascending). Any optimal answer is accepted.

---

## 2) Key observations

1. **Change variables** for each opponent:
   - \(d_i = a_i - b_i\) (difference contribution)
   - \(s_i = a_i + b_i\) (sum contribution)

   For a chosen set \(S\) (|S|=K):
   - \(D = \sum d_i = A - B\)
   - \(Ssum = \sum s_i = A + B\)

   Goal becomes:
   - minimize \(|D|\)
   - tie-break: maximize \(Ssum\)

2. Since \(a_i, b_i \in [0,50]\), we have \(d_i \in [-50, 50]\): **only 101 possible differences**.

3. **Dominance inside a difference group**:
   - If two opponents have the same \(d\), picking the one with larger \(s\) is always better (same effect on \(D\), better on \(Ssum\)).
   - Therefore, from each difference group we only ever need the **top K** opponents by \(s\) (because total picks is K).

   This shrinks candidates from up to 60000 down to at most \(101 \cdot K \le 2020\).

4. After reduction, we can do a knapsack-style DP over:
   - how many picked (1..K)
   - total difference \(D\) (range \([-50K, 50K]\), at most \([-1000,1000]\))

   and maximize \(Ssum\) for each reachable state.

---

## 3) Full solution approach

### Step A — Reduce N by grouping
For each opponent \(i\):
- compute \(d_i = a_i - b_i\)
- compute \(s_i = a_i + b_i\)

Group opponents by \(d_i\) (101 buckets).
In each bucket, sort by \(s_i\) descending and keep only top **K**.

Now we have at most ~2020 candidates.

---

### Step B — DP to select exactly K opponents
We want: among all ways to pick exactly K items,
- minimize \(|\sum d_i|\)
- tie-break by maximizing \(\sum s_i\)

Use a shifted-difference representation to avoid negative indices:
- let `OFFSET = 50`
- store `shifted_d = d + OFFSET` in \([0,100]\)

If we pick K items:
- `sumShifted = Σ(d+OFFSET) = D + K*OFFSET`
- so `D = sumShifted - K*OFFSET`
- minimizing \(|D|\) equals minimizing \(|sumShifted - K*OFFSET|\)

DP state. We index the count so that `dp[cnt]` means "exactly `cnt + 1` items selected":
- `dp[cnt][sumShifted]` stores a `State` with three fields:
  - `possible`: whether this combination is reachable,
  - `sum`: the **maximum** achievable `Ssum` for that state,
  - `indices`: the actual chosen indices, stored directly to reconstruct the answer (no separate parent array needed).
- Thus `dp[0]` corresponds to picking 1 item and `dp[k-1]` to picking K items.

Process candidates grouped by shifted diff. For each item \((shifted\_d, s, idx)\):
- transition: iterate `cnt` from `k-2` down to `0` (backwards, so an item is not reused), and for every reachable `dp[cnt][sumShifted]` relax `dp[cnt+1][sumShifted + shifted_d]` with the larger `Ssum`, copying the indices and appending `idx`;
- base case: seed the single-item state `dp[0][shifted_d]`, keeping the best `s` among items sharing the same shifted diff.

At the end, among all reachable `dp[k-1][sumShifted]`:
- choose one minimizing `abs(sumShifted - K*OFFSET)`
- tie: maximizing `Ssum`

Then recover:
- \(D = sumShifted - K*OFFSET\)
- \(A = (Ssum + D)/2\)
- \(B = (Ssum - D)/2\)

Read the stored indices, sort them, and print.

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int MAXV = 50;
const int OFFSET = MAXV;
const int MAX_SIZE = 2 * OFFSET + 1;
const int INF = (int)1e9 + 42;

struct State {
    bool possible = false;
    int sum = 0;
    vector<int> indices;
};

int n, k;
vector<pair<int, int>> ab;

void read() {
    cin >> n >> k;
    ab.resize(n);
    cin >> ab;
}

void solve() {
    // There is a direct DP solution with state dp[pos][balance][num_selected],
    // where the balance is O(K*MAXV), num_selected is O(K), and pos is O(N). At
    // every step we have 2 transitions - either select, or not. The overall
    // complexity is then O(N K^2 MAXV). This is a bit too slow, as MAXV is ~50,
    // K is 20, and N is around 60000. However, we can try speeding it up with
    // one key observation: N is too large for K = 20. We can group the numbers
    // into groups by A-B, and notice that we don't need to keep more than O(K)
    // items in each group - particularly the ones with largest value of A+B.
    // There are only O(MAXV) such groups, and this reduces N to O(K MAXV),
    // making the full complexity O(K^3 MAXV^2). This should be fast enough to
    // pass, although we might have to be a bit careful about the memory as we
    // do want to recover the solution.

    const int offset = OFFSET;
    const int max_diff = MAX_SIZE;
    const int max_sum = k * MAX_SIZE;

    vector<vector<pair<int, int>>> groups(max_diff);

    for(int i = 0; i < n; i++) {
        int a = ab[i].first;
        int b = ab[i].second;
        int diff = a - b + offset;
        int sum = a + b;

        groups[diff].push_back({sum, i + 1});
    }

    for(int i = 0; i < max_diff; i++) {
        sort(groups[i].begin(), groups[i].end(), greater<pair<int, int>>());
        if((int)groups[i].size() > k) {
            groups[i].resize(k);
        }
    }

    vector<vector<State>> dp(k, vector<State>(max_sum));

    for(int diff = 0; diff < max_diff; diff++) {
        for(auto [sum, idx]: groups[diff]) {
            for(int cnt = k - 2; cnt >= 0; cnt--) {
                for(int s = 0; s + diff <= max_sum - 1; s++) {
                    if(dp[cnt][s].possible &&
                       (!dp[cnt + 1][s + diff].possible ||
                        dp[cnt + 1][s + diff].sum < dp[cnt][s].sum + sum)) {
                        dp[cnt + 1][s + diff].possible = true;
                        dp[cnt + 1][s + diff].sum = dp[cnt][s].sum + sum;
                        dp[cnt + 1][s + diff].indices = dp[cnt][s].indices;
                        dp[cnt + 1][s + diff].indices.push_back(idx);
                    }
                }
            }

            if(diff < max_sum &&
               (!dp[0][diff].possible || dp[0][diff].sum < sum)) {
                dp[0][diff].possible = true;
                dp[0][diff].sum = sum;
                dp[0][diff].indices = {idx};
            }
        }
    }

    int best_diff = -1;
    int best_sum = -1;
    int min_balance = INF;

    for(int s = 0; s < max_sum; s++) {
        if(dp[k - 1][s].possible) {
            int balance = abs(s - offset * k);
            if(balance < min_balance ||
               (balance == min_balance && dp[k - 1][s].sum > best_sum)) {
                min_balance = balance;
                best_diff = s;
                best_sum = dp[k - 1][s].sum;
            }
        }
    }

    int a_total = (best_sum + best_diff - offset * k) / 2;
    int b_total = (best_sum - best_diff + offset * k) / 2;

    cout << a_total << ' ' << b_total << '\n';

    vector<int> result = dp[k - 1][best_diff].indices;
    sort(result.begin(), result.end());
    cout << result << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

# p366 - Computer Game
#
# Same approach:
# 1) Transform each opponent: d=a-b, s=a+b
# 2) Group by d (101 possibilities), keep top K by s in each group
# 3) knapsack-style DP for exactly K picks:
#    dp[cnt][sumShifted] = max Ssum, where cnt indexes "cnt + 1 items picked"
#    store chosen indices directly to reconstruct the answer
#
# Note: Python might be close to the time limit on some judges,
# but with the reduction to <= 2020 items and small DP it's typically fine.

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    k = int(next(it))

    ab = [(int(next(it)), int(next(it))) for _ in range(n)]

    MAXV = 50
    OFFSET = 50
    MAX_SIZE = 2 * OFFSET + 1     # 101 possible shifted diffs [0..100]
    max_diff = MAX_SIZE
    max_sum = k * MAX_SIZE        # max possible sum of shifted diffs over K picks

    # Group opponents by shifted diff; each entry is (a+b, index)
    groups = [[] for _ in range(max_diff)]
    for i, (a, b) in enumerate(ab, start=1):     # 1-based indices
        diff = a - b + OFFSET
        s = a + b
        groups[diff].append((s, i))

    # Keep only top K by (a+b) in each diff group
    for d in range(max_diff):
        groups[d].sort(reverse=True)
        if len(groups[d]) > k:
            groups[d] = groups[d][:k]

    # DP:
    # dp[cnt][sd] = best total (A+B) achievable by selecting (cnt+1) items
    #               with shifted-diff sum = sd
    # Store chosen indices for reconstruction.
    possible = [[False] * max_sum for _ in range(k)]
    bestsum  = [[0] * max_sum for _ in range(k)]
    choice   = [[None] * max_sum for _ in range(k)]  # None or list[int]

    for diff in range(max_diff):
        for s, idx in groups[diff]:

            # transitions for adding item to existing selections
            for cnt in range(k - 2, -1, -1):  # from k-2 down to 0
                for sd in range(0, max_sum - diff):
                    if not possible[cnt][sd]:
                        continue
                    nsd = sd + diff
                    nsum = bestsum[cnt][sd] + s
                    if (not possible[cnt + 1][nsd]) or (bestsum[cnt + 1][nsd] < nsum):
                        possible[cnt + 1][nsd] = True
                        bestsum[cnt + 1][nsd] = nsum
                        choice[cnt + 1][nsd] = choice[cnt][sd] + [idx]

            # base: selecting exactly 1 item
            if diff < max_sum:
                if (not possible[0][diff]) or (bestsum[0][diff] < s):
                    possible[0][diff] = True
                    bestsum[0][diff] = s
                    choice[0][diff] = [idx]

    # Select best among K picks (cnt index k-1)
    target_cnt = k - 1
    best_sd = -1
    best_s = -1
    best_balance = 10**18

    for sd in range(max_sum):
        if not possible[target_cnt][sd]:
            continue
        balance = abs(sd - OFFSET * k)  # equals |A-B|
        if balance < best_balance or (balance == best_balance and bestsum[target_cnt][sd] > best_s):
            best_balance = balance
            best_sd = sd
            best_s = bestsum[target_cnt][sd]

    # Recover A and B:
    D = best_sd - OFFSET * k  # A-B
    Ssum = best_s             # A+B
    A = (Ssum + D) // 2
    B = (Ssum - D) // 2

    res = sorted(choice[target_cnt][best_sd])
    out = []
    out.append(f"{A} {B}\n")
    out.append(" ".join(map(str, res)) + "\n")
    sys.stdout.write("".join(out))

if __name__ == "__main__":
    solve()
```
