Description

    古老的tracer部落最近推举dalong成为新一届的部落酋长，俗话说新官上任三把火，dalong上任后的第一件事情就是改善部落村民们的通信问题。tracer部落幅员辽阔，平时人们要互相通信都是用信鸽传递信息，这种方法使得信息的及时性大打折扣。毕业于“信息黄埔”的dalong通过自己高深的通信知识，决定为村民们建造一套通信系统，使得大家能够方便高效的通信。在建造通信系统前，我们先来看看tracer部落的地形：tracer部落有n户人家，而且有意思的是，这n户人家正好在一条直线上。

    dalong的通信系统需要在这n户人家中挑选出一家建立基站，然后跟其他n-1户的每个家庭建立一条单独的专用有线连接，出于安全考虑，任何一段电线都只为一户非基站人家传输数据。（比如有a,b,c三家，b在中间，基站在a，则需要建立ab，ac两条连接，且ab并不是ac的一部分）现在，dalong已经为n户家庭都配备了接收设备，他需要选择一个合适的家庭建造基站，使得铺设的电线总长度最小。但是，有些家庭不愿意在自己的家中建造基站。你的任务就是帮助他计算出最少需要多少电线。

Input

多组数据测试

对于每组数据，输入的第一行是1个正整数n(1 <= n <= 100000),表示tracer部落有n户人家。

输入的第二行是n个正整数a(0 <= a <= 1000000),第i个数表示第i个家庭的坐标。

输入的第三行也是n个整数b(0 <= b <= 1), b=0表示第i个家庭不可以建造基站，b=1表示第i个家庭可以建造基站。数据保证至少有一个家庭可以建造基站输入的最后是一个数0，表示输入结束，对于这组数据不用处理。

Output

对于每组数据，输出dalong最少需要铺设的电线总长度。答案保证小于2^31。 

Sample Input

41 2 3 41 1 1 151 2 3 5 41 1 0 1 10

Sample Output

47

---

用的方法较笨。

第一次用的暴力方法，当时想着就会超时，果然不出所料啊。

然后又做了改进。

先对坐标进行排序。可以发现，每次到下一个坐标时，可以根据上一个坐标得到的距离，迅速得到答案。大大优化了速度。

不知道还有么有更好的方法。

import java.io.BufferedInputStream; import java.util.Arrays; import java.util.Scanner; public class 高才生 {
   static int opt[]; static int[] bool = new int[1000000]; public static void main(String[] args) {
           Scanner s = new Scanner(new BufferedInputStream(System.in,2048)); int n; while((n=s.nextInt()) !=0){
   int[] arr1 = new int[n];             opt = new int[n]; for(int i=0; i