#494. 烽火传递
烽火传递
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
原题来自:NOIP 2010 提高组初赛 · 完善程序
烽火台是重要的军事防御设施,一般建在交通要道或险要处。一旦有军情发生,则白天用浓烟,晚上有火光传递军情。
在某两个城市之间有 座烽火台,每个烽火台发出信号都有一定的代价。为了使情报准确传递,在连续 个烽火台中至少要有一个发出信号。现在输入 和每个烽火台的代价,请计算总共最少的代价在两城市之间来准确传递情报。
输入格式
第一行是 ,表示 个烽火台和连续烽火台数;
第二行 个整数表示每个烽火台的代价 。
输出格式
输出仅一个整数,表示最小代价。
样例
输入样例
5 3
1 2 5 6 2
输出样例
4
在第 号烽火台上发信号。
提示
对于全部数据,。