Overview

By utilizing the fact that the number of items \(M\) is small (at most \(14\)), we can perform a DP where the set of sold items is represented by a bitmask.
However, since the number of visitors \(N\) is large, the key is to narrow down the candidates to only the “top \(M\) visitors with the highest profit” for each item.

Analysis

The profit when item \(j\) is sold to visitor \(i\) is:

\(V_{i,j} - C_j\)

Transactions with negative profit are not allowed, and transactions with \(0\) profit do not change the total profit whether we make them or not. Therefore, in the implementation, we only consider transactions with positive profit.

---

Naive DP is too slow

Since the number of items \(M\) is small, we might want to consider a DP where the set of sold items is represented by a bitmask.

For example, let:

\(dp[mask] =\) the maximum profit when the set of already sold items is \(mask\)

Suppose we process the visitors one by one.

In this case, since we try each item for each visitor, the time complexity would be approximately:

\(O(N \times M \times 2^M)\)

However, in the worst case, we have:

\(N = 10^5,\ M = 14\)

which gives:

\(10^5 \times 14 \times 2^{14}\)

This is too large to run within the time limit.

---

We only need to consider the top \(M\) people for each item

The key observation is as follows:

For each item \(j\), it is sufficient to keep only the top \(M\) visitors with the highest profit as candidates.

This is because the number of sold items is at most \(M\), so at most \(M\) visitors will buy items in the optimal solution.

For example, suppose an item \(j\) is sold to a visitor \(i\) who is not in the top \(M\) visitors for that item.

Consider the top \(M\) visitors with the highest profit for item \(j\). Visitor \(i\) is not among them.

At most \(M\) visitors are used in the entire optimal solution.
If all of the top \(M\) visitors have already bought something, then adding visitor \(i\) who buys item \(j\) would mean a total of \(M+1\) visitors are used. This is impossible.

Therefore, there must be at least one person among the top \(M\) visitors who has not bought anything yet.
Even if we redirect the sale of item \(j\) to that person, the profit from item \(j\) will not decrease.

Thus, even if we only keep the top \(M\) visitors with the highest profit for each item, the value of the optimal solution does not change.

---

As a result, the number of candidate visitors becomes at most:

\(M \times M = M^2\)

Since \(M \leq 14\), this is at most \(196\) people.
With this number of candidates, the bitmask DP will easily run within the time limit.

Algorithm

1. Collect visitors with positive profit for each item

For each item \(j\), calculate the profit when sold to visitor \(i\):

\(p = V_{i,j} - C_j\)

Only if \(p > 0\), add \((p, i)\) to the candidate list for item \(j\).

---

2. Keep only the top \(M\) visitors with the highest profit for each item

For each item \(j\), sort the candidate list in descending order of profit and keep only the top \(M\) visitors.

Add the remaining visitors to the global candidate set.
Since the same visitor can be a candidate for multiple items, we store the profit of each item for each visitor in an array.

---

3. Bitmask DP on the candidate visitors

Process the candidate visitors one by one.

Let:

\(dp[mask] =\) the maximum profit when the set of sold items is \(mask\), using only the visitors processed so far.

Here, \(mask\) is an \(M\)-bit integer, where the \(j\)-th bit is \(1\) if item \(j\) has already been sold.

For each visitor, the choices are:

• Do not buy anything
• Buy one item \(j\) that has not been sold yet

The transition is as follows:

Let \(w\) be the profit of item \(j\):

\(dp[mask \cup \{j\}] = \max(dp[mask \cup \{j\}], dp[mask] + w)\)

This transition is valid only when item \(j\) is not included in \(mask\).

Finally, since we do not need to sell all items, the answer is:

\(\max dp[mask]\)

Complexity

Let \(L_j\) be the number of candidates with positive profit for each item \(j\).

• Time Complexity: \(O(NM + \sum_j L_j \log L_j + M^3 2^M)\)
  • Calculating the profits from the input takes \(O(NM)\).
  • Sorting the candidates for each item takes \(O(\sum_j L_j \log L_j)\).
  • The number of candidate visitors is at most \(M^2\), so the DP takes \(O(M^3 2^M)\) time.
• Space Complexity: \(O(NM + M2^M + M^3)\)

Under the constraints \(NM \leq 2 \times 10^5\) and \(M \leq 14\), this is sufficiently fast.

Implementation Details

• Transactions with a profit of \(0\) or less do not improve the answer, so we do not include them in the candidates.

• In the DP transition, we must ensure that the same visitor does not buy multiple items.

  • To achieve this, we can refer to the current dp as old and update a copied array new.
  • If we overwrite dp directly, it might allow a single visitor to buy multiple items.

• The answer is max(dp), not dp[(1 << M) - 1].

  • This is because we do not necessarily have to sell all items.

• Precomputing masks_without[j] as a list of masks where item \(j\) has not been sold yet allows us to skip the bitwise checks during the transitions.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0
    N = data[idx]
    M = data[idx + 1]
    idx += 2

    C = data[idx:idx + M]
    idx += M

    profits_by_item = [[] for _ in range(M)]

    for i in range(N):
        for j in range(M):
            p = data[idx] - C[j]
            if p > 0:
                profits_by_item[j].append((p, i))
            idx += 1

    cand = {}

    for j in range(M):
        lst = profits_by_item[j]
        if len(lst) > M:
            lst.sort(reverse=True)
            lst = lst[:M]

        for p, i in lst:
            if i not in cand:
                cand[i] = [0] * M
            cand[i][j] = p

    if not cand:
        print(0)
        return

    size = 1 << M
    masks_without = []
    for j in range(M):
        b = 1 << j
        masks_without.append([mask for mask in range(size) if (mask & b) == 0])

    visitor_edges = []
    for arr in cand.values():
        edges = []
        for j, w in enumerate(arr):
            if w:
                edges.append((j, 1 << j, w))
        visitor_edges.append(edges)

    dp = [0] * size

    for edges in visitor_edges:
        old = dp
        new = old.copy()

        for j, b, w in edges:
            mw = masks_without[j]
            for mask in mw:
                v = old[mask] + w
                to = mask + b
                if v > new[to]:
                    new[to] = v

        dp = new

    print(max(dp))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.