Adam is working in a large hierarchical organization, where every employee, except the CEO, is either a supervisor or a sub-ordinate or both. Every employee will be identified by Employee ID. CEO of the company has 1 as his employee id. Every employee will get the salary (S) in accordance with their level and their performance. Given the data about the all the above mentioned details, your task is to find out the number of sub-ordinates with salary less than Adam.

Note: 
1. If an employee appears at two different levels, then consider the level which is near (best) to the CEO.
2. An employee is considered as sub-ordinate, if Adam is a direct or indirect supervisor to the said employee.

Input Format: 
Input consists of three parts, viz.
1. First Line contains, number of employees (N), number of supervisor-subordinate relationships (M) and Adam's employee id (A)
2. Next M lines follow, each line contains two employee Ids I, J which represents that I is a supervisor of J.
3. Salaries of N employees, delimited by space

Output Format: 
Print the total number of employees who are sub-ordinates to Adam and have salary less than Adam's.

Constraints:
1<=N<=50
1<=M<=1000
1<=I, J<=N
1<=S<=50000

Sample Input and Output

Input

Output

5 5 2
1 2
2 3
2 4
4 5
5 3
1500 2000 1500 2500 1800

2