Beacon Tower
Time: 1 s
Memory: 535.16 MB
Memory: 535.16 MB
The beacon tower is an important military defense facility, generally built on major transportation routes or dangerous locations. Once there is a military situation, thick smoke is used during the day, and fire signals are used at night to transmit military information.
There are \(n \) beacon towers between two cities, and each beacon tower has a certain cost to send a signal. In order to accurately transmit the information, at least one beacon tower must send a signal within a continuous \(m\) beacon towers. Now given \(n, m \) and the cost of each beacon tower, calculate the minimum total cost to accurately transmit the information between the two cities.
Input
The first line contains \(n, m\), indicating the number of beacon towers \(n\) and the number of consecutive beacon towers \(m\);The second line contains \(n\) integers representing the cost of each beacon tower \(a_i\)
Constraint
For all data, \(1 \leq m\leq n \leq 2 \times 10^{5}\) and \(1 \leq a_i \leq 1000\).
Output
Output a single integer, representing the minimum cost.
Examples
| Input | Output |
|---|---|
|
5 3
1 2 5 6 2 |
4
|
| Input | Output |
|---|---|
|
10 4
1 2 3 4 4 5 4 3 2 1 |
7
|
| Input | Output |
|---|---|
|
6 6
1 2 3 3 4 2 |
1
|
| Input | Output |
|---|---|
|
5 1
1 2 3 4 5 |
15
|
Problem Info
| Problem ID | 567 |
| Time Limit | 1000 ms |
| Memory Limit | 548000 KB |
| Moderators | MJ5aif |
Statistics
Submit
You need to Login or Registration for submit your solution