Training Site
Sideways banner

Hot Chocolate

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 1.1 seconds

It is a bright, clear January morning at the yearly NZOI camp. In the dining area, all the informatics students are lined up, waiting to receive true happiness in the form of hot chocolate. But times are tight, and with only two hot chocolate machines, you must ensure that the (hot chocolate related) hopes and dreams of the young students are not crushed.

Each hot chocolate machine has a capacity of drinks, measured in cups. Each student requires a certain number of cups of hot chocolate, and has a different preference for one hot chocolate machine over the other. That is, each student gains a certain amount of happiness units from each machine - the two happiness values may be different between the machines for any particular student. Additionally, some students have a strong preference for one machine, which means they will only drink from that machine.

As a responsible camp leader, your moral principles dictate that no student can miss out on hot chocolate. You will assign each student to get their desired fill from one (and exclusively one) of the hot chocolate machines. You also daren't assign a student with a strong preference to the machine that they won't drink from - you don't want another repeat of [REDACTED]. Find the maximum total happiness from the students that you can achieve with this method, or determine that it is impossible to make everyone happy.


  • The first line will contain two space-separated integers L and R, the capacities of the left and right machines respectively.

    • 0 \le L, R \le 8,000
  • The next line will contain a single integer N , the number of students at the camp.

    • 1 \le N \le 250
  • The following N lines will each contain three space-separated integers, c_i, l_i, and r_i, representing a student. c_i is the number of cups that this student will drink, and l_i and r_i are the happiness units that the student will derive from drinking from the left and right machines, respectively. If the student has a strict preference for the left machine, then r_i = -1. Similarly, if the student has a strict preference for the right machine, then l_i = -1.

    • 1 \le c_i \le 8,000
    • 1 \le l_i, r_i \le 1,000,000, or r_i = -1, or l_i = -1 (but never l_i = r_i = -1)


You should output a single integer H, the largest possible total happiness if all students can get their drink. If that is impossible, output Camp is cancelled (without the quotes).


  • Subtask 1 (+15%): R = 0
  • Subtask 2 (+15%): For all i, either r_i = -1 or l_i = -1 (that is, every student has a strong preference)
  • Subtask 3 (+35%): L, R \le 150 and N \le 30
  • Subtask 4 (+35%): No further restrictions apply


Python programmers should submit solutions with Python 3.6 (PyPy 7.3) selected instead of Python 3.8, as it may make the submission run faster. We cannot guarantee that all solutions submitted for Python 3.8 will pass with the given time limit.

  • Sample Input 1

    4 6
    3 1 6
    2 6 4
    2 5 -1

    Sample Output 1

  • Sample Input 2

    9 6
    5 9 8
    6 12 4
    3 9 44
    4 8 20
    2 12 5

    Sample Output 2

    Camp is cancelled