Jack Frost

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 128M

Problem type

After becoming a Guardian, Jack Frost thought he would be bolstering faith in the children around the world. Little did he know, it was all a scheme so Santa could increase unpaid labour and lay off some elves. After decades of making presents instead of being tasked with protecting the children, Jack has had enough.

To make Santa happy, Jack Frost decides to buy some presents. The goal of his presents is to make Santa feel a certain way, in particular a happiness of X. Any higher or any lower, and Santa just might not change his mind. Before buying the gifts, Santa's happiness is 0.

There are N different gifts types that are available for purchase in the North Pole, the i^{th} of which will increase Santa's happiness by a_i. He can buy each gift type as many times as he wants. For each gift Jack buys, he can also choose to break it, which will decrease Santa's happiness by a_i.

Given the constraints, will Jack make Santa happy?


1 \le N \le 10^6

1 \le X \le 10^{12}

1 \le a_i \le 10^9

Input Specification

The first line contains two integers, N and X.

The next line contains N space-separated integers, a_1, a_2, ... , a_N.

Output Specification

Output Santa is happy if there is a way, and Santa is mad if there is not.

Sample Input 1

3 24
1 6 10

Sample Output 1

Santa is happy

Sample Explanation 1

Jack can buy gift type 3 twice, and type 2 once, to give Santa a happiness of 26. Then, by purchasing gift type 1 twice, and breaking both, he decreases Santa's happiness to 24.

24 = 10 + 10 + 6 - 1 - 1

Sample Input 2

5 12
5 228 3 56 69

Sample Output 2

Santa is happy

Sample Input 3

5 19
18 6 24 63 123

Sample Output 3

Santa is mad


There are no comments at the moment.