FCAR

All submissions for this problem are available.
Cars of future no longer need fuel to run, but they are fitted with special engines which can only operate in one of the two modes at a time ,either go up the road, or go down the road.
There are N towns in country. i^{th} town is at height H[i] (1 ≤ i ≤ N) above the sea level.
Changing mode of the car requires permissions from mayor of the town you are currently at. Mayor of i^{th} town charges amount C[i] (1 ≤ i ≤ n) for giving permission to change mode of the car.
These N towns are connected by R bidirectional roads. Initially no mode is set, so you need permissions to set a mode.
You have to travel from town 1 to N, in minimum amount of cost. Print minimum money required to make the travel. If it is impossible print 1.
Note:
 Go up the road mode: when you are at town A and want to go to town B, where H[A] <= H[B]
 Go down the road mode: when you are at town A and want to go to town B, where H[A] >= H[B]
 If you continue with the same mode, you do not need to take permissions from mayor.
Input
 First line contains two space separated integer N and R, number of towns and number of roads.
 Next line contains N space separated integer where i^{th} integer is H[i], height of i^{th} town.
 Next line contains N space separated integer where i^{th} integer is C[i], cost charged by mayor of i^{th} town to give permission for changing the mode.
 Next R lines contains two space separated integer u and v, specifying there is a bidirectional road between town u and v.
Output
Print minimum cost required for travel. If it is impossible print 1.
Constraints
 2 ≤ N ≤ 100000
 1 ≤ R ≤ 500000
 1 ≤ H[i] ≤ 10^{9}
 1 ≤ C[i] ≤ 10^{9}
Example
Input: 6 6 10 5 7 15 20 6 1 1 1 1 1 1 1 2 2 3 3 6 1 4 4 5 5 6 Output: 2
Explanation
There are two paths from 1  6
P1: (1, 2, 3, 6)
You need to pay $1 to mayor of town 1 to chose down mode. (H[1] >= H[2])
You need to pay $1 to mayor of town 2 to chose up mode. (H[2] <= H[3])
You need to pay $1 to mayor of town 3 to chose down mode. (H[3] >= H[6])
Total cost = $3
P2: (1, 4, 5, 6)
You need to pay $1 to mayor of town 1 to chose up mode. (H[1] <= H[4])
You continue with the previous up mode. (H[4] <= H[5])
You need to pay $1 to mayor of town 5 to chose down mode. (H[5] >= H[6])
Total cost = $2
So minimum money required is $2.
Author:  amanmittal 
Editorial  http://discuss.codechef.com/problems/INSQ15_F 
Tags  amanmittal, dijkstra, fcar, insq2015 
Date Added:  6092015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, TEXT 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 