욱제는 도박쟁이야!!

욱제는 라스베이거스에서 이름난 베팅꾼이고, 즐겨 하는 게임은 동전 뒤집기다. 이 게임에 쓰는 동전은 양면에 절댓값이 같고 부호가 다른 정수가 한 면에 하나씩 적혀 있다. 동전끼리는 적힌 수의 절댓값이 다를 수 있다.

한 플레이어는 두 번의 라운드를 치른다. 두 라운드 모두 같은 동전으로 진행하고, 딜러는 라운드마다 $N$개의 동전을 임의로 섞어 일렬로 놓는다. 이때 각 동전의 앞뒤 방향도 바뀔 수 있다. 첫 번째 라운드에서는 위를 향한 면에 적힌 수의 합이 최대가 되도록 동전을 뒤집어야 하고, 두 번째 라운드에서는 그 합이 최소가 되도록 뒤집어야 한다. (첫 번째 라운드의 합) - (두 번째 라운드의 합)이 그 플레이어가 얻는 점수다.

욱제는 엄지, 검지, 중지를 써서 언제나 연속한 세 개의 동전을 한 번에 뒤집는다. 연속한 세 개를 뒤집지 않으면 이길 수 없다고 믿기 때문에, 실패하는 일 없이 항상 연속한 세 개만 뒤집는다. 세 칸짜리 범위가 배열의 양 끝을 벗어나도 되므로, 끝에 있는 동전 한 개만 뒤집거나 끝에 있는 동전 두 개만 뒤집는 것도 가능하다. 뒤집는 횟수에는 제한이 없다.

욱제는 최고의 베팅꾼이라 언제나 얻을 수 있는 가장 높은 점수를 얻는다. 욱제가 이번 게임에서 얻는 점수를 구하라.

첫째 줄에 동전의 수 $N$이 주어진다. ($1 \le N \le 10000$)

둘째 줄에 첫 번째 라운드에 놓인 동전 $N$개의 위를 향한 면에 적힌 수가 순서대로 주어진다.

셋째 줄에 두 번째 라운드에 놓인 동전 $N$개에 대해 같은 값이 순서대로 주어진다.

동전에 적힌 수는 절댓값이 $10000$ 이하인 정수다.

욱제가 이번 게임에서 얻을 점수를 출력한다.

첫 번째 예제의 첫 번째 라운드는 -2, -7, -8을 한 번에 뒤집으면 합이 최대가 된다.

두 번째 라운드는 1, 8, -7을 뒤집고 이어서 7, 5, 2를 뒤집으면 합이 최소가 된다.