There are ~n~ items for Ray to buy on Taobao, but he can only select ~k~ items to buy (since he has limited space). He wants to buy items based on how big of a discount he gets, and you have to calculate the total savings he makes from buying ~k~ items with the largest discounts.

To approach this problem, it would make sense to first get the input which has the original price and the discounted price, then store the discount. Once we've stored the discount, we can get the best discounts (up to ~k~) and keep a running total, before printing it out.

To implement the solution, we can first use a dynamic array (i.e., vector) to store the ~n~ discounts, which is the original minus the discounted price. Once all discounts have been stored, the array can be sorted such that the largest discount value is first and the smallest discount value is last.

Once our array of discounts is sorted, we pick the first ~k~ elements and add them to a running total, which are the highest discounts you could get. We then print the resulting total.

Consuming the input is ~O(n)~, given we have ~n~ items. Sorting is ~O(n \log n)~, while selecting ~k~ elements is ~O(k)~. This gives us a time complexity of ~O(n + n \log n + k)~, but since ~k < n < n \log n~, the final time complexity is ~O(n \log n)~.

Since we use a vector to store our ~n~ discounts, the space complexity is ~O(n)~.

C++ solution:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> priceDiffs(n);
    for (auto& x: priceDiffs) {
        int orig, discount;
        cin >> orig >> discount;
        x = orig - discount;
    }

    sort(priceDiffs.rbegin(), priceDiffs.rend());
    cout << accumulate(priceDiffs.begin(), priceDiffs.begin()+k, 0) << endl;
}

Python solution:

n,k = map(int, input().split())

items = [map(int, input().split()) for _ in range(n)]
items = [original-discount for original,discount in items]
items.sort(reverse=True)

print(sum(items[:k]))