22050번 - Сбор монет 다국어

Недавно Виталик установил себе на телефон новую игру. Персонаж этой игры ходит по ленте, которая разбита на n клеток. Изначально все клетки пусты, и персонаж находится в одной из клеток. Каждую секунду в каждой клетке появляется некоторое количество новых монет в дополнении к старым, которые уже там находятся. За одну секунду главный герой может совершить одно из двух действий. Либо он остается на месте и собирает новые монеты, которые появятся в этой клетке. Либо переходит в соседнюю клетку и собирает те монеты, которые уже были там, а также те, которые появятся в ней в эту секунду.

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

Первая строка содержит три целых числа n, t и start (1 ≤ n ≤ 250, 1 ≤ t ≤ 250, 1 ≤ start ≤ n) — количество клеток, количество ходов, которые может сделать игрок, а также стартовую позицию. Вторая строка содержит n целых чисел a₁, ..., a_n (1 ≤ a_i ≤ 300). i-е число обозначает количество монет, которые появляются каждую секунду в клетке i.

Выведите единственное число — максимальное количество монет, которые может собрать игрок.