Card Game (APCS 2023-10 Intermediate)

Points 100 1.0s 256M

There is a table with \(n\) rows and \(m\) columns. Every cell contains a card with an integer value. Each value that appears in the table occurs exactly twice.

Suppose two cards both have value \(x\). If they are in the same row or the same column and there is no unremoved card between them, you may remove both cards and gain \(x\) points. A removed cell becomes empty, and empty cells do not block other cards.

You may repeat this operation and choose any removable pair at each step. Find the greatest total score you can obtain.

Input

The first line contains two integers \(n\) and \(m\), the number of rows and columns of the table.

The next \(n\) lines contain \(m\) integers each and describe the card values.

Constraints

  • \(1\le n\le20\)
  • \(1\le m\le40\)
  • Every card value is between \(0\) and \(1000\), inclusive
  • Every value that appears occurs exactly twice
  • \(nm\) is even

Output

Output one integer: the greatest total score you can obtain.

Scoring

The time limit for each test case is \(1\) second; your score is the sum over the test cases you pass. The subtasks are:

Subtask Points Additional constraints
1 60 \(n=1\)
2 40 No additional constraints

Sample Input 1

1 8
0 2 3 3 0 2 5 5

Sample Output 1

8

Sample Explanation 1

The pairs with values 3 and 5 can both be removed, for a maximum score of \(3+5=8\).

Sample Input 2

3 6
0 2 3 8 0 2
1 1 4 4 5 7
5 6 3 8 6 7

Sample Output 2

29

Sample Explanation 2

The pairs with values 1, 4, 7, 3, 8, and 6 can be removed in that order. Their values sum to \(1+4+7+3+8+6=29\).

Source

APCS October 2023 Programming Problem 2, "Card Game"

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.