死ぬがよい。

ストーリー

ここは魔術大国Grimwar。魔法により統治された平和な国である。

この国は以前、隣国のNOW_MAN_ZAWと宗教戦争を行っていたが、

電脳世界の住人、雛ちゃんの仲裁によりお互いの良さを認め合い、

良好な関係を結ぶまでに至った。

しかしこの日、両国に対しその辺のどこの馬の骨とも知らぬ新興宗教都市、

『Hogeism』が突如攻め込んできた。

その圧倒的理論武装と彼らの持つ『三幻神』の力によりGrimwarは即時壊滅、

幸い犠牲者は出なかったもののGrimwarの姫Alice達はNAW_MAN_ZAWに退避せざるを得なかった。

NAW_MAN_ZAWの防壁は強固であり、かつ『力のコーヒー』の力を用いたNAW_MAN_ZAWの兵士の力により、

Hogeismの内部への侵攻を防ぐことには成功したが、都市は甚大な被害を受け、彼らは防壁の外にテントを張り始めた。

このままでは、GrimwarとNAW_MAN_ZAWの人々は兵糧攻めにより滅びてしまうだろう！！

見かねたAlice達は、都市内の神殿において、再び電脳世界から雛ちゃんを呼び出した。

和平交渉の為、神殿から出ようとした雛ちゃんだが、ここであることに気付く。

神殿の中は雛ちゃんを呼び出した際の衝撃により倒壊した瓦礫に満たされ、

雛ちゃんが移動する為には瓦礫を移動させなければならない！！

神殿内は縦5*横4マスのブロックに区切ることができ、雛ちゃんや瓦礫はこのマスの一部を占有している。

瓦礫はGrimwarの魔法とNAW_MAN_ZAWの力の合体技により上下左右に移動させることができ、

各方向に1マス移動させる際に魔力を1消費する。

なお、雛ちゃんも各方向に1マス移動する際に魔力を1消費する。

瓦礫を動かし、雛ちゃんが神殿の外に出れるようになった時の、消費した魔力の最小を求めよ。

問題

神殿内は縦5＊横4マスに区切られており、左上から右下にかけて(H0,W0)から(H4,W3)と座標が振られている。

雛ちゃんや瓦礫はこのマスの一部を占有しており、マスを占有する要素は以下の通りである。

雛ちゃん：縦2*横2マスを占有する。
縦長の瓦礫：縦2*横1マスを占有する。
横長の瓦礫：縦1*横2マスを占有する。
普通の瓦礫：縦1*横1マスを占有する。

瓦礫や雛ちゃんはその方向に瓦礫や雛ちゃんが存在しない時に限り上下左右に移動することができ、

移動には魔力を1消費する。神殿からはみ出ることは当然不可能である。

各種占有要素の数と、それぞれの座標がN回与えられるので、

それぞれの入力において雛ちゃんの占有するマスが以下のようになるように移動を行ったときの消費した魔力の最小を出力せよ。

移動終了時の雛ちゃんの位置

＊＊＊＊
＊＊＊＊
＊＊＊＊
＊雛雛＊
＊雛雛＊

入力形式

最初の一行に、与えられる入力パターンの数 N , 縦2マスブロックの数 A , 横2マスブロックの数 B , 1マスブロックの数 C が空白区切りで与えられる。

N A B C

以下N回、次の入力が繰り返される。

雛ちゃんの初期位置 pos_h,pos_w

縦2マスブロックの初期位置 A_pos_h_i , A_pos_w_i

横2マスブロックの初期位置 B_pos_h_i , B_pos_w_i

1マスブロックの初期位置 C_pos_h_i , C_pos_w_i

pos_h pos_w
A_pos_h1 A_pos_w1
..
A_pos_hA A_pos_wA
B_pos_h1 B_pos_w1
..
B_pos_hB B_pos_wB
C_pos_h1 C_pos_w1
..
C_pos_hC C_pos_wC

制約

• 1 ≦ N ≦ 100000
• 0 ≦ A*2+B*2+C ≦ 16
• 瓦礫や雛ちゃんが神殿をはみ出したり、重複して配置されることはない。

入出力例

入力例1

1 4 1 4
0 1
0 0
0 3
2 0
2 3
2 1
3 1
3 2
4 0
4 3

出力例1

100

今回の入力における瓦礫等の配置は以下のようになる。

縦雛雛縦
縦雛雛縦
縦横横縦
縦普普縦
普空空普

---

入力例2

3 0 2 10
0 1
2 0
2 2
0 0
0 3
1 0
1 3
3 0
3 1
3 2
3 3
4 0
4 3
0 1
3 0
3 2
0 0
0 3
1 0
1 3
2 0
2 1
2 2
2 3
4 0
4 3
3 1
0 0
0 2
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 3

出力例2

48
41
0