In the year 20XX, the IOI will finally be held in JOI Town, JOI Country, and a party will be held to commemorate this. There are $A$ dogs (numbered $1, 2, \dots, A$) and $B$ cats (numbered $1, 2, \dots, B$) in JOI Town. You have decided to invite all $A + B$ animals to the party.

There are $N$ "friendship groups" between the dogs and the cats. The $i$-th friendship group consists of dogs with numbers from $P_i$ to $Q_i$ (inclusive) and cats with numbers from $R_i$ to $S_i$ (inclusive). Each friendship group has a positive integer called the "friendship level" associated with it. The friendship level of the $i$-th group is $T_i$. A single dog or cat may belong to multiple friendship groups, and some dogs or cats may not belong to any friendship group at all.

You are very good friends with the dog numbered $C$, and you have already succeeded in inviting that dog. You have decided to invite the remaining dogs and cats by repeating the following actions:

• If all $A + B$ animals have already been invited, terminate.
• For each dog or cat that has not yet been invited, consider the "happiness value" when inviting them. The happiness value is the maximum friendship level among all friendship groups to which the dog or cat belongs and which contain at least one dog or cat that has already been successfully invited. If no such friendship group exists, the happiness value is $0$.
• Choose the dog or cat with the highest happiness value. If there are multiple such dogs or cats, prioritize dogs, and if there is still no single choice, prioritize the one with the smaller number.
• If the happiness value of the chosen dog or cat is $0$, the invitation process fails and terminates. Otherwise, you succeed in inviting the chosen dog or cat.

You have decided to calculate the outcome of this invitation method in advance.

Task

Given the number of dogs $A$, the number of cats $B$, the number of the dog $C$ with whom you are very good friends, and information about the $N$ friendship groups, determine whether you will succeed in inviting all $A + B$ animals. If you succeed, calculate the sum of the happiness values of the dogs or cats chosen at each step.

Input

Read the following from standard input:

• The first line contains three integers $A, B, C$ ($1 \le C \le A$), representing the number of dogs, the number of cats, and the number of the dog you are very good friends with, respectively.
• The second line contains an integer $N$, representing the number of friendship groups.
• The $(2+i)$-th line ($1 \le i \le N$) contains five integers $P_i, Q_i, R_i, S_i, T_i$ ($1 \le P_i \le Q_i \le A$, $1 \le R_i \le S_i \le B$), representing that the $i$-th friendship group consists of dogs with numbers from $P_i$ to $Q_i$ and cats with numbers from $R_i$ to $S_i$, and has a friendship level of $T_i$.

Output

Output a single integer on a single line to standard output:

• If you succeed in inviting all $A + B$ animals, output the sum of the happiness values of the dogs or cats chosen at each step.
• If the invitation process fails midway, output $-1$.

Constraints

• $1 \le A \le 1\,000\,000\,000$
• $1 \le B \le 1\,000\,000\,000$
• $1 \le N \le 100\,000$
• $1 \le T_i \le 1\,000\,000\,000$

Subtasks

1. (30 points) $A \le 1\,000$, $B \le 1\,000$, $N \le 2\,000$.
2. (50 points) $N \le 2\,000$.

Examples

Input 1

5 6 3
4
2 4 1 3 20
1 2 2 4 40
4 5 2 3 30
4 4 4 6 10

Output 1

280

Input 2

10 10 1
2
1 5 1 5 3
6 10 6 10 4

Output 2

-1