• [1153] Hero May Die But the King Will Never

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • There's an old saying - Hero may die but the king will never(英雄会死,而王绝不).
    You may know that the hero is protecting the King, so he may die.
    The King trains countless heros, and they will be attacked for M seconds. Every hero can be exposed to the attack of monster for at most S seconds. After a hero finishes his protecting, another hero will replace after at least B seconds.
    For example, the King let hero A insist for 4 seconds, and at the 4th second, the hero A will back home and the next hero will go to protect the King at (4 + B)th second or later. That means, from 4th second to (4 + B)th second or more, the king will be exposed to the attack of the monster.
    The king asks you to tell him how to arrange the heros that his damage will be minimum.
  • 输入
  • This problem has several cases. Input until EOF.
    For each case, the first line is 3 integers S, B and M. (0 < M <= 1000, 0 < S <= M, 0 < B <= M).
    Then follows a line with M integers. The ith integer Di indicates the damage at ith second. (0 < Di <= 1000)
  • 输出
  • For each case, you should output the minimum damage the King will suffer.
  • 样例输入
  • 2 5 9
    10 10 1 1 1 1 1 10 10
  • 样例输出
  • 5
  • 提示
  • 来源
  • XadillaX
  • 操作