버섯

바이트 숲(Bytean Forest)에 큰 비가 내렸다. 버섯 채집을 좋아하는 바이트만(Byteman)은 이 기회를 놓치지 않고 버섯을 따러 나섰다.

숲에는 여러 개의 빈터를 지나는 오솔길이 하나 있고, 각 빈터에는 버섯이 자라 있다. 길 위에서 이웃한 두 빈터 사이의 간격은 모두 같아서, 이웃한 빈터로 걸어가는 데에는 항상 15분이 걸린다. 어떤 빈터에 도착하면 바이트만은 그곳의 버섯을 즉시 모두 딴다. 한 번 딴 버섯은 정확히 30분 뒤에 다시 완전히 자라나며, 다시 자란 버섯은 전부 다시 딸 수 있다.

바이트만은 첫 번째 빈터에서 출발하여 15분마다 이웃한 빈터로 이동한다(제자리에 머무를 수는 없다). 산책은 $t$개의 15분 구간 동안 이어지므로 바이트만은 모두 $t$번 이동하고, $0, 15, 30, \dots, 15t$분 시점에 자신이 서 있는 빈터의 버섯을 딴다. 산책은 길 위의 어느 빈터에서 끝나도 좋다.

각 빈터의 버섯 개수와 산책의 길이가 주어질 때, 바이트만이 가장 잘 움직였을 때 딸 수 있는 버섯의 최대 개수를 구하여라.

첫째 줄에 빈터의 수 $n$과 산책의 길이 $t$가 주어진다 ($1 \le n, t \le 10^6$). 여기서 $t$는 15분짜리 구간의 개수, 즉 바이트만이 이동하는 횟수이다.

둘째 줄에는 길을 따라 놓인 빈터들의 버섯 개수 $a_1, a_2, \dots, a_n$이 순서대로 주어진다 ($1 \le a_i \le 10^6$). 바이트만은 첫 번째 빈터에서 출발한다. 어떤 버섯을 딴 시점으로부터 정확히 30분이 지난 순간에는 그 버섯을 이미 다시 딸 수 있다.

바이트만이 산책하는 동안 딸 수 있는 버섯의 최대 개수를 정수 하나로 한 줄에 출력한다.

$n = 5$, $t = 4$, 버섯 개수가 3 4 3 5 1인 경우를 생각하자. 60분(= 4구간) 동안의 최적 경로에서 바이트만은 버섯 18개를 딴다: 0분에 3개, 15분 뒤에 4개, 30분 뒤에 3개, 45분 뒤에 5개, 그리고 마지막으로 60분 뒤에 다시 3개이다. 30분에 땄던 빈터의 버섯이 정확히 30분 뒤인 60분에 다시 완전히 자라나 있으므로 한 번 더 딸 수 있다.