提示: 欢迎访问OurACM平台。
Problem 2178 礼物分配

Accept: 93    Submit: 355
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

在双胞胎兄弟Eric与R.W的生日会上,他们共收到了N个礼物,生日过后他们决定分配这N个礼物(numv+numw=N)。对于每个礼物他们俩有着各自心中的价值vi和wi,他们要求各自分到的礼物数目|numv-numw|<=1,并且各自所衡量的礼物价值的差值|sumv-sumw|尽可能小,现在他们想知道最小的差值是多少。

Input

第一行为一个整数表示数据组数T。 接下来T组数组,每组数据第一行为一个整数N。(N<=30) 第二行有N个整数,表示Eric所衡量的每个礼物的价值vi。(1<=vi<=10000000) 第三行也有N个整数,表示R.W所衡量的每个礼物的价值wi。(1<=wi<=10000000)

Output

对于每组数据,输出最小的差值。

Sample Input

1 3 1 2 3 4 2 1

Sample Output

1

Source

FOJ有奖月赛-2014年11月

Submit  Back  Status  Discuss