Profit Maximization
Problem
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 j 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.
Constraints
1≤N≤103
0≤Pi≤105
Time Limit: 1
Memory Limit: 256
Source Limit:
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).
