대평원

$1$km를 $100$분에 이동하는 개미가 대평원 위의 시작점에서 도착점으로 이동하려고 한다. 단, $x$축과 $y$축에 평행하게 이동해야 하고 구릉지에서는 이동 시간이 늘어날 수 있다. 여러분은 시작점, 도착점, 구릉지들, 그리고 구릉지마다 1km를 이동하는 데 걸리는 시간이 주어졌을 때 이 개미가 시작점에서 도착점까지의 가장 빠르게 이동할 수 있는 시간을 계산하라.

구릉지는 $x$축과 $y$축에 평행한 변으로 구성된 직사각형 모양이며 직사각형마다 $1$km를 이동하는 데 걸리는 시간이 주어진다. 이 이동시간은 직사각형의 내부에만 적용되고 변에는 적용되지 않는다. 또한 서로 다른 두 직사각형은 겹치지 않으며 시작점, 도착점, 그리고 서로 다른 직사각형들의 꼭지점 $x$좌표들은 모두 정수이며 겹치지 않는다. $y$좌표들도 마찬가지로 모두 정수이며 겹치지 않는다. 시작점과 도착점은 항상 직사각형의 외부에 존재한다.

위 예제는 km 단위 좌표에 km당 이동 시간이 $200$분인 직사각형-왼쪽 아래 좌표가 $(0,1)$이고 오른쪽-위 좌표가 $(5,2)$과 km당 이동 시간이 $1\,000$분인 직사각형-왼쪽 아래 좌표가 $(4,3)$이 고 오른쪽-위 좌표가 $(9,4)$를 표시한 것이다. 시작점이 A이고 도착점이 B인 경우와 시작점이 C이고 도착점이 D인 경우의 최단시간 경로가 표시되어 있으며 각각 최단시간은 $700$분과 $1\,000$분이다.

여러분은 다음 함수를 구현해야만 한다.

long long shortest_path(pair<int, int> src, pair<int, int> dst, vector<pair<int, int>> p1, vector<pair<int, int>> p2, vector<int> w); 단 한 번 호출되는 함수이다. src와 dst는 시작점과 도착점이다. 각 직사각형의 왼 쪽 아래점은 p1에 오른쪽 위의 점은 p2에 주어진다. 주어진 값을 이용하여 src로부터 dst까지의 최단시간을 구하여 return 한다.

문제

제한