34332번 - 해피 밀푀유

문제

보경이는 원래 개발자를 꿈꿨지만, 취업에 실패한 뒤 밀푀유 가게를 차렸다.

밀푀유는 총 $N$개의 층으로 구성되어 있으며, 맨 아랫부분이 1ドル$층이고 맨 윗부분이 $N$층인 구조이다. 각 층 $i$에는 $S_i$개의 토핑이 존재한다.

가게를 연 뒤, 보경이는 손님에게 더 나은 만족도를 주기 위해 밀푀유의 구성을 고민했다. 그러던 중 손님들이 밀푀유를 위에서부터 아래로 한 층씩 차례대로 먹는다는 사실을 알게 되었다.

이를 본 보경이는 아래층에 존재하는 임의의 토핑이 위층에 존재하는 임의의 토핑보다 더 높은 당도를 가지도록 밀푀유를 만들기로 했다.

이를 위해, 맨 위층을 제외한 밀푀유의 층 $i(1 \le i < N)$에 대해 다음 조건을 만족해야 한다.

• 층 $i$ 에 속한 모든 토핑의 당도 최솟값은 층 $i+1$에 속한 모든 토핑의 당도 최댓값보다 커야 한다.

각 토핑의 당도는 0ドル$ 이상 $M$ 이하의 정수이며, 전체 토핑의 당도 합은 정확히 $T$가 되어야 한다.

또한, 보경이는 당도 차이가 갑자기 커지면 너무 달아서 손님이 불쾌함을 느낄 수 있다는 점도 고려했다.

손님은 $i$ $(i < N)$ 번째 층에 있는 당도 $x$의 $j$번째 토핑을 먹을 때, 이전에 먹었던 $k$ $(k > i)$층에 있는 당도 $y$의 임의의 토핑과 비교하여 $y < x$인 경우마다 $x - y$만큼의 불쾌함을 느낀다.

이 토핑에 대한 불쾌감 지수를 모두 합한 것을 $p_{ij}$라 하고, 손님이 느끼는 전체 불쾌함의 총합 $P$는 모든 $p_{ij}$의 합이다.

보경이는 최대한 손님에게 불쾌함을 적게 주는 밀푀유를 개발하려고 한다. 손님이 이 밀푀유를 먹었을 때 느끼는 전체 불쾌함의 총합 $P$의 최솟값을 구해보자!

입력

첫째 줄에 밀푀유의 최대 층수 $N$과 토핑의 최대 당도 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100,000円;\ N \le M \le 150,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐, 각층에 존재하는 토핑 수 $S_i$가 주어진다. $(1 \le S_i \le 150)$

마지막 줄에 목표하는 전체 토핑의 당도 합인 $T$가 주어진다. $(0 \le T \le 10^{13})$

입력되는 모든 수는 정수이다.

출력

전체 토핑의 당도 합이 $T$가 되는 밀푀유를 만들 수 없다면 첫째 줄에 Sad를 출력한다.

만들 수 있다면, 첫째 줄에 Happy를 출력한 뒤, 바로 다음 줄에 전체 불쾌함의 총합을 나타내는 정수 $P$의 최솟값을 출력한다.

제한

힌트