Problem O: LY Find Max GCD

Problem O: LY Find Max GCD

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 76  Solved: 8
[Submit] [Status] [Web Board] [Creator:]

Description

If A is a sequence of 2*n integers, its pairing is divide A into n pairs of consecutive elements and taking the sum of each pair.

For example, the pairing of A = { 1,2,3,4 } is the sequence { 1+2, 3+4} = { 3, 7 }.



LY are given a A consisting of 2*n positive integers. You are going to perform the following steps:

  • Create a new sequence B that is a permutation of A.
  • Find the sequence C that is the pairing of B.
  • Compute the greatest common divisor of all elements of C and denote it D.

Find and return the largest possible value of D (over all possible choices of B).

each test at most  10

A length 2*n, n>=1&&n<=15

A[i] >=1 && A[i] <=1e9


Input

2

1 2 3 4


Output

5


Sample Input Copy

1
3 8

Sample Output Copy

11