One day, Tamata the treasure hunter visited an old, mysterious tunnel. Inside the tunnel he discovered a sequence of N diamonds inlaid on the wall shining at him. Each two adjacent diamonds are exactly 1 meter apart. He also noticed that there is a some-kind-of detector, faced to those array of diamonds. After took a serious check, Tamata finally found out how the detector worked. Simply concluding, a this-kind-of detector could detect M meters wide (i.e. M consecutive diamonds) each time, and then enumerate the “shining value” for the diamonds. Once the detected “shining value” was strictly less than a certain value, say K, then it would explode and destroy all the things including diamonds and Tamata. “Shining values” are simple to calculate, X diamonds together in a scene would provide shining value X.
Knowing perfectly about the detector, Tamata soon estimated the value of diamonds, and started thinking how much value of diamonds could he take away……
Hakuna Matata! It’s time for you to write a program which reads values of each diamonds and find out the largest value that can be taken away.
There are multiple test cases in the input file. For each test case:
First line contains three integers N, M, and K (1<=K<=M<=N<=1000) denoting the number of diamonds, the detecting width, and the exploding lower bound respectively.
The second line contains N positive integers d_i(1<=d_i<=1000000) seperated by at least one space.
For each test case please output the maximum total value of diamonds. There is no need to print any blank lines between test cases.
9 5 3 3 1 4 1 5 9 2 6 5 9 5 4 3 1 4 1 5 9 2 6 5
22 12
For the first sample input, Tamata can take away the diamonds with values 3, 4, 9, 6.
Migrated from old NTUJ.
Tmt
| No. | Testdata Range | Score |
|---|