T-shirts

During the Programming Olympiad finals, each of the $N$ contestants is always given a t-shirt as is customary. However, the judges are sometimes a bit stressed out with making last minute changes to the problem sets (only changes, mind you – the judges never wait until the day before the contest to make a problem).

This means that when the judges order the t-shirts, they may not look that carefully on what t-shirt sizes the contestants have. After all, who can distinguish a size XS t-shirt from an XL t-shirt? The judges certainly couldn’t, but it appears that the contestants can when they try putting their new t-shirts on. Since the judges never learn to plan properly, this will surely be a problem next year as well. But right now it is your problem.

While each contestant has a preferred size, they can wear t-shirts in an interval of sizes. More specifically, the $i$:th contestant (starting from 0) can wear a t-shirt in any size at least $L[i]$ but at most $H[i]$ (both limits inclusive). Here, each size has been assigned an integer so that a higher integer means a larger size. Your task is to assign t-shirts to the contestants, so that as many contestants as possible will get a t-shirt that he or she can wear. The judges have ordered exactly $N$ t-shirts, and the size of the $i$:th t-shirt is $T[i]$.

Example

There are $N = 3$ contestants. The first contestant can wear t-shirts between sizes $3$ and $7$, the second contestant can wear t-shirts in sizes $3$ to $5$, and the last contestant can only wear a size $6$ t-shirt.

The three t-shirts have sizes $4, 6, 8$. Since nobody can wear the last t-shirt, at most two t-shirts can be assigned to the contestants. This can also be achieved, for example by giving the first t-shirt (size $4$) to the first contestant, and the second t-shirt (size $6$) to the last contestant. Thus the answer is 2.

Task

Your task is to compute the maximum number of contestants who can get a t-shirt that he or she can wear. You should implement the function tshirt(N, L, H, T).

• tshirt(N, L, H, T) - this function will be called exactly once by the judge.

  • N: an integer - the number of contestants (as well as t-shirts).

  • L: an array with $N$ integers. L[i] ($0 \le i < N$) is the smallest size the $i$:th contestant can wear.

  • H: an array with $N$ integers. H[i] ($0 \le i < N$) is the largest size the $i$:th contestant can wear.

  • T: an array with $N$ integers. T[i] ($0 \le i < N$) is the size of the $i$:th t-shirt.

  • $0 \le L[i] \le H[i] \le \max (T)$

  • The function should return an integer, the maximum number of contestants who can get a t-shirt assigned to them.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/tshirts.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

Input format

The sample judge reads input in the following format:

• line $1$: N

• line $2$: L[0] L[1] .. L[N - 1]

• line $3$: H[0] H[1] .. H[N - 1]

• line $4$: T[0] T[1] .. T[N - 1]

Output format

The judge writes a single line containing the return value of tshirt(N, L, H, T).

3
3 3 6
7 5 6
4 6 8

2