Shortest Path in a Multi-Floor Building with Elevators

You are given a building with n floors. Each floor i has a specified number of rooms. The rooms on a floor are arranged in a row and are numbered consecutively from left to right. You can move horizontally between adjacent rooms on the same floor, and each such move counts as one step.

In addition, there are m elevators. Each elevator directly connects two rooms in different floors, and you can use an elevator to move between these two rooms (the move counts as one step). The elevator moves are bidirectional.

You are given the number of floors, the number of elevators, a list of the number of rooms on each floor, and a list of elevators specified as 4 integers f1, r1, f2, r2 where an elevator connects the room r1 on floor f1 and the room r2 on floor f2.

Your task is to determine the minimum number of moves needed to go from a starting room on the 1^st floor to a target room on the n^th floor. If it is impossible to reach the target room, output -1.

Mathematically, if you denote the starting room as located at floor 1 and room s, and the target room as located at floor n and room t, you need to compute the minimum number of moves required. Moves can be represented as transitioning between adjacent room indices on the same floor or via an elevator connecting rooms on different floors. The relation for horizontal moves on a floor can be expressed as:

$$|r_j - r_i|$$

where \(r_i\) and \(r_j\) are the room numbers on the same floor.

inputFormat

The input is given from standard input (stdin) as follows:

 First line: two integers, n and m, representing the number of floors and the number of elevators.
 Second line: n integers, where the i-th integer represents the number of rooms on floor i.
 Next m lines: each line contains 4 integers, f1 r1 f2 r2, representing an elevator connecting room r1 on floor f1 and room r2 on floor f2.
 Last line: two integers, s and t, where s is the starting room number on the 1st floor and t is the target room number on the nth floor.

outputFormat

Output a single integer which is the minimum number of moves needed to reach the target room from the starting room. If it is impossible to reach the target room, output -1.

## sample

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

4