Adott két vektor v₁=(x₁,x₂,...,x_n) és v₂ = (y₁,y₂,...,y_n). A két vektor skalárszorzata egyetlen szám: x₁*y₁+x₂*y₂+...+x_n*y_n.

Tegyük fel, hogy a vektorok koordinátáit szabadon permutálhatjuk (tetszőleges sorrendben írhatjuk). Határozzuk meg az így kapható minimális skalárszorzatot.

Írjunk programot, ami megadja a skalárszorzat lehetséges értékei közül a minimálisat.

A bemenet első sora a tesztesetek T számát tartalmazza. (1 <= T <= 1000). Ezután T teszteset következik, három-három sorban kódolva. Az első sor n értékét adja meg (1 <= n <= 800), majd az x_i és y_j koordináták következnek, egy-egy sorban, szóközökkel elválasztva (-100000 <= x_i, y_j <= 100000).

A kimenet T sort tartalmaz, mindegyik sorban a megfelelő tesztesetre kapható minimum szerepel.

Bemenet	Kimenet
2 3 1 3 -5 -2 4 1 5 1 2 3 4 5 1 0 1 0 1	Case #1: -25 Case #2: 6

A feladat forrása: Google Code Jam 2008 1A (online tesztelő)

Algoritmusok: mohó algoritmus

megoldás