L. Chasing Hamoosh
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Due to severe destruction in Syria, many residents have fled and left their homes empty. The thief Hamoosh takes advantage of this to steal iron from the abandoned buildings, but the policeman Homsi spots him and initiates a pursuit.

There are $$$N$$$ buildings arranged in a circle, numbered $$$1$$$ to $$$N$$$ in clockwise order. For $$$1\le i \lt N$$$, the building following building $$$i$$$ is $$$i+1$$$, and the building following building $$$N$$$ is $$$1$$$. The $$$i$$$-th building contains $$$W_i$$$ units of iron.

You must choose the initial starting building for Hamoosh and the initial starting building for Homsi. At time $$$0$$$, both are placed on their respective starting buildings. In each turn, they move simultaneously in the clockwise direction: Hamoosh jumps forward by exactly $$$A$$$ buildings, and Homsi jumps forward by exactly $$$B$$$ buildings.

Hamoosh steals all $$$W_i$$$ units of iron from any building $$$i$$$ he lands on for the first time. If Hamoosh and Homsi land on the same building at the exact same moment, Hamoosh is immediately caught and the game ends. When caught, Hamoosh is arrested before he can steal the iron from that specific building.

You must assign the starting positions such that Homsi is guaranteed to eventually catch Hamoosh. Under this restriction, what is the maximum amount of iron Hamoosh can collect before being caught?

Input

The first line contains three integers $$$N$$$, $$$A$$$, and $$$B$$$ ($$$1\le N\le 5000$$$, $$$1\le A,B\le N$$$) — the number of buildings, the number of buildings Hamoosh jumps per turn, and the number of buildings Homsi jumps per turn.

The second line contains $$$N$$$ integers $$$W_1,W_2,\dots,W_N$$$ ($$$0\le W_i\le 10^9$$$) — the amount of iron in each building.

Output

Print a single integer — the maximum amount of iron Hamoosh can collect before being caught.

Example
Input
5 2 3
10 20 30 40 50
Output
140