Description

At the end of each year, the hotel manager receives all pre-orders for the honeymoon room for the next year. Each pre-order contains the following necessary information: arrival date, departure date, and customer identity.

Because the hotel has only one honeymoon room and can host at most one newlywed couple at the same time, not all booking requests can be satisfied.

When some booking requests overlap in time, we say that these booking requests conflict.

For those pre-orders that do not conflict with any other booking request, they will certainly be accepted, because this is good for both the hotel and the customers.

For conflicting booking requests, the manager must reject some of them to ensure that the hotel operates in an orderly manner.

Obviously, for booking requests that conflict within the same time period, the manager can accept at most one of them. The manager may also reject all booking requests within the same time period, because this can avoid disputes among customers.

After making the decision, the manager needs to announce the whole plan publicly to show fairness. This is a decision that must be made carefully, because it involves many factors. The first thing the manager considers is of course profit. He definitely hopes to obtain as much income as possible. However, while pursuing economic benefits, the hotel should also consider social benefits. It should not be too profit-driven and must also take customers’ feelings into account. If the manager decides which bookings to accept or reject purely from the perspective of maximizing profit, it will cause dissatisfaction.

The manager has a consultant who studied marketing. The consultant told the manager that a compromise can be made: give up the most profitable plan, and instead adopt the plan with the $k$-th largest profit. Through accurate market analysis, he found the best value of $k$ and told it to the manager.

Now please help the manager: from a large number of booking requests, under the principles above, find the plan with the $k$-th largest profit. The manager will decide which booking requests to accept and reject based on this plan.

Of course, there may be several plans with the same profit. In that case, they are considered the same as the $i$-th largest profit plan and are not distinguished. For example, if there are $3$ plans with income $3$ and $2$ plans with income $2$, then all plans with income $3$ belong to the largest profit, and all plans with income $2$ belong to the second largest. And so on.

Assume that all check-in and check-out registrations are handled at $12$ noon.

Input Format

The first line of the input file contains two numbers, $k$ and $t$. Here, $k$ indicates that we need to choose the plan with the $k$-th largest profit; $t$ indicates that customer identities are divided into $t$ categories.

The second line contains an integer $y$, indicating the year of the next year.

The third line contains an integer $r$, indicating that there are a total of $r$ booking requests.

In the following $r$ lines, each line is one booking request in the format: m1/d1 TO m2/d2 id;

Here, $m_1,d_1$ and $m_2,d_2$ represent the arrival and departure dates respectively. $id$ is an integer ($1 \leq id \leq t$) used to identify the customer’s identity category.

The last $t$ lines each contain an integer $P_{i}$ ($1 \leq i \leq t$), representing the daily rate for the honeymoon room for customers with identity code $i$.

Example: a couple arrives on June $1$ and leaves on June $3$. If their daily rate is $m$ yuan/day, then they stay for two days in total and need to pay $2m$ yuan.

Output Format

The output file contains only one integer $p$, representing the hotel’s total annual revenue under the plan with the $k$-th largest profit. If the plan with the $k$-th largest profit does not exist, output $-1$.

2 1
2000
4
1/1 TO 1/2 1
2/1 TO 2/2 1
3/1 TO 3/2 1
3/1 TO 3/3 1
1

3

Hint

Constraints:

$1 \leq k \leq 100$，$1 \leq t \leq 100$，$0 \leq r \leq 20000$，$1 \leq P_{i} \leq 32767$

Translated by ChatGPT 5