/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
整数 A,B,X,Y が与えられます。
二次元平面上にコマが置かれています。はじめコマは座標 (0,0) にあります。
あなたは以下の操作を 0 回以上何回でも行うことができます：
- 今コマがある座標を (x,y) として、座標 (x-1,y),(x+1,y),(x,y-1),(x,y+1) のいずれかにコマを移動させる。
k 回目 (k \geq 1) に行う操作にかかるコストは k の偶奇によって異なり、それぞれ以下の通りです：
- k が奇数のとき：今コマがある座標を (x,y) として、座標 (x-1,y),(x+1,y) に移動させる場合のコストは A、座標 (x,y-1),(x,y+1) に移動させる場合のコストは B である。
- k が偶数のとき：今コマがある座標を (x,y) として、座標 (x-1,y),(x+1,y) に移動させる場合のコストは B、座標 (x,y-1),(x,y+1) に移動させる場合のコストは A である。
コマを座標 (X,Y) に移動させるために必要なコストの総和の最小値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 2\times 10^5
- 1\le A,B\le 10^9
- -10^9\le X,Y\le 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
i 番目 (1\le i\le T) のテストケース \text{case}_i は以下の形式で与えられる。
A B X Y
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
入力例 1
5 1 2 -1 2 8 5 0 0 7 13 9 4 1 1 0 100 31 9 -74 -60
出力例 1
4 0 103 100 1332
1 番目のテストケースについて考えます。
以下のように移動することでコストの総和が 4 になります：
- コマを座標 (0,0) から座標 (-1,0) に移動させる。コストが 1 かかる。
- コマを座標 (-1,0) から座標 (-1,1) に移動させる。コストが 1 かかる。
- コマを座標 (-1,1) から座標 (-1,2) に移動させる。コストが 2 かかる。
コストの総和が 4 未満でコマを座標 (-1,2) に移動させることはできないので、1 行目には 4 を出力してください。
Score : 450 points
Problem Statement
You are given integers A,B,X,Y.
A piece is placed on a two-dimensional plane. Initially, the piece is at coordinate (0,0).
You can perform the following operation zero or more times:
- Let the current coordinate of the piece be (x,y). Move the piece to one of the coordinates (x-1,y),(x+1,y),(x,y-1),(x,y+1).
The cost of the k-th operation (k \geq 1) depends on the parity of k, as follows:
- If k is odd: Let the current coordinate of the piece be (x,y). The cost of moving to (x-1,y) or (x+1,y) is A, and the cost of moving to (x,y-1) or (x,y+1) is B.
- If k is even: Let the current coordinate of the piece be (x,y). The cost of moving to (x-1,y) or (x+1,y) is B, and the cost of moving to (x,y-1) or (x,y+1) is A.
Find the minimum total cost required to move the piece to coordinate (X,Y).
T test cases are given; solve each one.
Constraints
- 1\le T\le 2\times 10^5
- 1\le A,B\le 10^9
- -10^9\le X,Y\le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
The i-th (1\le i\le T) test case \text{case}_i is given in the following format:
A B X Y
Output
Output the answers for the test cases in order, each on a separate line.
Sample Input 1
5 1 2 -1 2 8 5 0 0 7 13 9 4 1 1 0 100 31 9 -74 -60
Sample Output 1
4 0 103 100 1332
Consider the first test case.
The following moves cost 4 in total:
- Move the piece from (0,0) to (-1,0). This costs 1.
- Move the piece from (-1,0) to (-1,1). This costs 1.
- Move the piece from (-1,1) to (-1,2). This costs 2.
It is impossible to move the piece to (-1,2) with a total cost less than 4, so output 4 on the first line.