You have to travel to different villages to make some profit. In each village, you gain some profit. But the catch is, from a particular village i, you can only move to a village j if and only if i<j and the profit gain from village is a multiple of the profit gain from village i You have to tell the maximum profit you can gain while traveling.
Input format The first line contains a single integer N denoting the total number of villages. The second line contains N space-separated integers, each denoting the profit gain Pi from village i
Output format Print the maximum profit you can gain.
Sample Input 6 1 2 3 4 98
Sample Output 15
Explanation The maximum profit 15 can be achieved by following the path with villages at index (0, 1, 3, 5) with profit gain (1, 2, 4, 8)