Задача состоит из трех подзадач: за решение подзадачи F1 вы получите 8 баллов, за решение подзадачи F2 вы получите 15 баллов, за решение подзадачи F3 вы получите 10 баллов.

Манао разработал модель, предсказывающую цены акций некоторой компании на протяжении следующих n дней. Теперь он хочет получить максимальную прибыль, используя результаты этой модели. К сожалению, торговый счет Манао имеет следующие ограничения:

• В любой момент времени, Манао может иметь либо 0, либо 1 акцию.
• Продажа или покупка акций может быть произведена лишь раз в день.
• В течение следующих n дней ему позволено произвести покупку акций не более k раз.

В этой задаче мы будем называть сделкой процесс покупки акции в некоторый день i и ее сохранения до дня j > i, в который акция будет продана. Предыдущие ограничения можно записать следующим образом: Манао разрешено сделать не более k непересекающихся сделок на протяжении n дней, для которых модель Манао предсказала цены акций.

Хотя имея возможность держать на руках более одной акции или производить более k сделок, Манао и смог бы получить больше прибыли, у него все равно есть шанс разбогатеть, учитывая что его модель делает точные предсказания. Например, зная наперед все цены, Манао может дождаться дня с низкой ценой акций, купить одну акцию и ждать дня с высокой ценой, в который он ее продаст, и повторять это k раз в течение n дней.

Тем не менее, для Манао недостаточно иметь просто хороший алгоритм купли-продажи, он хочет выработать оптимальную стратегию для максимизации прибыли при данных ограничениях. Помогите ему достичь этой цели, написав программу, которая определит, когда покупать и продавать акции, чтобы достичь максимально возможной прибыли.