Problem Description

Treeone, who has been reincarnated in a different world, decides to earn money by taking on escort missions for merchants as an adventurer.

In the Takahashi Kingdom, where he has been reincarnated, there are $ N $ cities besides the capital. Each city is numbered $ 1, 2, ..., N $. It takes $ T_i $ days to travel between the capital and city $ i $.

There are $ M $ escort missions from the capital to cities other than the capital. In the $ i $-th mission, the merchant departs from the capital on day $ A_i $ and arrives at city $ X_i $ on day $ A_i + T_{X_i} $.

There are also $ L $ escort missions from cities other than the capital to the capital. In the $ i $-th mission, the merchant departs from city $ Y_i $ on day $ B_i $ and arrives at the capital on day $ B_i + T_{Y_i} $.

Treeone cannot take multiple missions on the same day, including departure and arrival days. Also, he does not move between cities without taking a mission.

The reward for each mission is 1 gold coin. From these missions, choose the missions that will earn the most gold coins. Calculate the number of gold coins Treeone can earn.

Note that Treeone starts in the capital and it does not matter where he ends up after completing all chosen missions.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ L $ $ T_1 $ $ T_2 $ $ ... $ $ T_N $ $ X_1 $ $ A_1 $ $ X_2 $ $ A_2 $ $ : $ $ X_M $ $ A_M $ $ Y_1 $ $ B_1 $ $ Y_2 $ $ B_2 $ $ : $ $ Y_L $ $ B_L $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3

Sample Input #2

1 2 2
0
1 1
1 2
1 1
1 3

Sample Output #2

2

Notes/Hints

Constraints

• $1 \leq N, M, L \leq 10^5$
• $0 \leq T_i \leq 10^9$
• $1 \leq X_i \leq N$
• $1 \leq A_i \leq 10^9$
• $1 \leq Y_i \leq N$
• $1 \leq B_i \leq 10^9$
• No mission is given more than once.
• All inputs are integers.

Partial Points

• If you solve the dataset where $ N = 1 $, you will be awarded 30 points.

Sample Explanation 1

By taking the following missions, Treeone can earn 3 gold coins:
- Depart from the capital on day 2 and arrive at city 2 on day 3.
- Depart from city 2 on day 4 and arrive at the capital on day 5.
- Depart from the capital on day 6 and arrive at city 1 on day 9.

Sample Explanation 2

This input example satisfies the partial points constraint. Note that Treeone cannot take multiple missions on the same day, including departure and arrival days.

见题面 Input 部分

见题面 Output 部分