Hot Chocolate

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.

Input

• 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$)

Output

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).

Subtasks

• 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

Note:

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.