Блог

Есть N автобусных остановок, и на каждой автобусной остановке стоит[i] человек. Все в группе держатся вместе, так что либо все прыгают в автобус, либо ни один человек этого не делает.

Кроме того, сначала вы должны подобрать людей из группы 1, затем из группы 2 и так далее. Пассажиры не часто путешествуют, поэтому группа 1 уезжает до того, как присоединится группа 2.

Технология изменения размера, хотя и очень полезная, производит много дыма, поэтому правительство решило ограничить ее использование до B раз в день.

Даже вам не нравится, что ваш автобус пуст, поэтому вы решаете измерить полезность вашего автобуса по количеству свободных мест в нем в течение дня. Чем меньше мест будет потрачено впустую, тем счастливее вы будете.

Учитывая группы людей на каждой автобусной остановке, найдите и верните минимальную сумму общего потраченного пространства, используя вашу технологию изменения размера до B раз в день.

Примечание: Необходимо, чтобы количество пассажиров в автобусе было меньше или равно вместимости автобуса.

Формат ввода:

Первый аргумент ввода содержит целочисленный массив A, представляющий количество людей во всех группах. Второй аргумент ввода содержит целое число B, представляющее количество раз, когда вы можете использовать технологию изменения размера. Формат Вывода:

Возвращает целое число, представляющее минимальную сумму общего потерянного пространства. Ограничения:

 1 <= N <= 400
0 <= A[i] <= 1e6
1 <= B < N
Examples:

Input 1:
A = [10, 20]
B = 0

Output 1:
10
 

Пояснение 1:
Вы начинаете с автобуса 20-го размера.
Группа 1 содержит 10 человек, поэтому вы тратите 10 мест впустую. (Потраченное впустую пространство 10).
Группа 2 состоит из 20 человек, так что вы не тратите впустую ни одного места. (Потраченное впустую пространство 0).

 Input 2:
A = [1, 2, 3]
B = 1

Output 2:
1
 

Пояснение 2:
Вы начинаете с автобуса 2-го размера.
Группа 1 содержит только 1 человека, поэтому вы тратите место впустую. (Потраченное впустую пространство 1).
Группа 2 состоит из 2 человек, поэтому вы не тратите впустую ни одного свободного места. (Потраченное впустую пространство 0).
Вы меняете размер шины на 3.
Группа 3 состоит из 3 человек, поэтому вы не тратите впустую ни одного свободного места. (Потраченное впустую пространство 0).