Easy Dijkstra :p

5

4 votes
Maths, Easy
Problem

You are standing at point (x1,y1) in an infinite 2D plane. You have to go to point (x2,y2) in minimum cost.
The allowed moves are :
(x,y) -> (x,y-1) or (x,y+1) or (x-1,y) or (x+1,y), costing an amount A.
(x,y) -> (x-1,y-1) or (x-1,y+1) or (x+1,y-1) or (x+1,y+1), costing an amount B.

Input Format
The first line contains the number T.
The following T lines contain 6 numbers each : x1, y1, x2, y2, A, B.

Output Format
Output the answer for each testcase in a newline.

Constraints
1<=T<=10000
-1e9<=x1,y1,x2,y2<=1e9
1<=A,B<=1e9

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Testcase 1: The optimal path is (0,0) -> (1,1) with cost 6. 

Testcase 2: The optimal path is (0,0) -> (0,1) -> (1,1) with cost 2. 

Editor Image

?