Radio-frequency identification (RFI

Radio-frequency identification (RFID) uses
electromagnetic fields to automatically identify and
track tags attached to objects. With RFID, we can
manage items in wareho use easily and efficiently.
Instead of checking each item manually with
traditionally methods, such as barcode or QR code, we
can use an RFID scanner to automatically detect the
IDs of all items in a warehouse.
Intelligent Corporation of Production and Commerce
(ICPC) has a sequence of N warehouses, organized as a row in HiTech Park. The i
th warehouse
contains wi items.
ICPC intends to re-organize all items in warehouses so that ICPC can have available space for
its new business. As each item is attached an RFID tag, there is no need to manually check out
an item from a warehouse or check in an item to a new warehouse.
A robot is used to move all items from a warehouse to either its previous or next adjacent
warehouse. Only when that warehouse is empty can a robot begin its task to empty another
warehouse. On average, it takes 1 second to move 1 item from a warehouse to its adjacent
warehouse.
Compute the minimum time required to move items between warehouses so that finally at
most M warehouses contain items (other warehouses are all empty).
Input
The first line of input contains two integers N and M, separated by a space. (1 ≤ N ≤ 1500, 1 ≤
M ≤ 100)
The second line contains N positive integers that are the number of items in each warehouse.
The number of item in a warehouse is no more than 210. Initially, there is no empty warehouse.
Output
Display a single positive integer that is the minimum time required (in seconds) so that at most
M warehouses contain items.