Opening Treasure Boxes (APCS 2023-06 Expert)

2.0s 256M

There are \(n\) boxes and \(m\) key types numbered from \(0\) to \(m-1\). Each box requires all of its specified \(k\) key types and contains \(k\) key types as rewards. Keys are reusable and are never consumed. Given your initial keys, find the maximum number of distinct boxes you can open.

Input Format

The first line contains \(n,m,k\). The next line contains \(t\) followed by the \(t\) initial key types. The following \(n\) lines give the \(k\) required key types of each box. The next \(n\) lines give the \(k\) reward key types of the same boxes in the same order.

Output Format

Print the maximum number of boxes that can be opened.

Constraints

\(1\le n,m\le100000\), \(1\le k\le\min(5,m)\), \(0\le t\le m\). Key types on each individual line are distinct. A key type is required by at most \(60\) boxes.

Scoring

  • 20 points: \(n,m\le100\), \(k=1\).
  • 20 points: \(k=1\).
  • 60 points: No additional restrictions.

Each scored test is worth 5 points.

Sample Input 1

5 5 1
2 0 1
0
2
4
3
1
1
2
4
3
3

Sample Output 1

3

Sample Input 2

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

Sample Output 2

5

Source

APCS 2023-06 public archive version: k734。

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.