일 왜 함?

시간 제한1.122초메모리 제한1122 MB

요약

준성이 N개 암호화폐의 가격 변화 규칙을 따를 때, T일 동안 코인마다 하루에 한 단위씩 거래해 얻을 수 있는 최대 이익을 구합니다.

문제

일하기는 싫고 한탕만 노리는 준성이는 가상화폐 $N$ 개 종목의 시세를 분석하기 시작했다! 준성이가 분석한 결과는 다음과 같다. $P_i$ 는 $i$ 번 가상화폐의 가격이다.

$P_i$ 는 $1$ 아니면 $2$ 다.
$P_1$ 은 하루가 지날 때마다 바뀐다. 즉 $P_1$ 이 $1$ 이라면 $2$ 가 되고, $2$ 라면 $1$ 이 된다.
$P_{i+1}$ 은 하루가 지날 때마다 어제의 $P_1, P_2, \dots, P_i$ 가 모두 $2$ 라면 바뀌고, 그렇지 않다면 바뀌지 않는다. $(1 \leq i \leq N-1)$
위 조건을 제외하고 $P_i$ 가 바뀌는 경우는 없고, 모든 종목의 가상화폐는 무한히 많다.

거대 자본이 투입되어 분석 결과가 무용지물이 되는 경우를 고려하여 준성이는 거래를 진행할 때 하루에 한 종목당 1개의 가상화폐만 사거나 팔려고 한다.

준성이는 부지런해서 항상 가상화폐의 가격이 갱신되자마자 거래를 시작하며, 거래를 진행하는 시간은 무시할 수 있을 만큼 짧다. 준성이가 의도한 거래가 실패하는 경우는 없다. 즉, 준성이가 가상화폐를 사려고 하면 반드시 살 수 있고, 팔려고 하면 즉시 팔 수 있다.

분석 결과가 모두 들어맞고 준성이의 자본이 항상 가상화폐를 살 수 있을 만큼 충분하다고 가정하자. $T$ 일간 거래를 진행하여 얻을 수 있는 최대 이익을 구하자.

첫 번째 줄에 정수 $N$ 과 $T$ 가 공백을 사이에 두고 주어진다. $(1 \leq N \leq 111222;\ 1 \leq T \leq 10^{12})$

두 번째 줄에 준성이가 거래를 시작한 날의 $P_i$ 가 순서대로 공백 없이 주어진다.

첫 번째 줄에 문제의 정답을 출력한다.

거래가 종료된 시점에 준성이가 갖고 있는 가상화폐는 이익에 포함하지 않는다.