Subtask 1

Each coupon has a pair ~(K, M)~, the number of keyboards and monitors that it can buy. ~(0, 0)~ coupons cannot buy anything, and can be ignored. ~(1, 0)~ and ~(2, 0)~ coupons should always be used to buy keyboards, while ~(0, 1)~ and ~(0, 2)~ should be used for monitors. When deciding how to spend the ~(1, 1)~ coupons, first count how many keyboards and monitors you will get from the ~(2, 0)~ and ~(0, 2)~ coupons, then use any ~(1, 1)~ coupons for the item that you have less of.

Time Complexity: ~\mathcal{O}(N)~

Subtask 2

There are ~2~ ways to spend each coupon, which makes ~2^N~ ways in total. Loop through all ~2^N~ possibilities and choose the best option.

Time Complexity: ~\mathcal{O}(N \cdot 2^N)~

Subtask 3

First, group the coupons by value. For each group, sort them in order of decreasing ~K_i~ (which is also increasing ~M_i~, since they have the same value). Then, the coupons at the front will have the highest ~K_i~, while the ones at the back have the highest ~M_i~. Suppose you used a coupon on monitors, and used another coupon after it for keyboards. If instead you used the first one for keyboards and the second for monitors, you would have gotten more monitors and keyboards. Therefore, you should never use a coupon for monitors when a coupon behind it is used for keyboards, because there will always be a better way to use the coupons. In other words, the optimal way to spend the coupons is to use the first ~i~ for keyboards (for some ~0 \le i \le G_V~, where ~G_V~ is the size of the group of coupons with value ~V~), and the last ~G_V-i~ coupons on monitors.

Using a precalculated prefix sum array, we can loop through to find the best choice of ~i~ in ~\mathcal{O}(G_V)~ time. Do this for each group, and choose the group with the best final result.

Time Complexity: ~\mathcal{O}(N \log N)~