30051번 - 일 왜 함?

문제

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

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

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

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

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

입력

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

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

출력

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

제한

노트

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