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?
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.
Print a single integer — the maximum amount of iron Hamoosh can collect before being caught.
5 2 310 20 30 40 50
140
| Название |
|---|


