Description

Yumis has recently been playing Hearthstone.

In Hearthstone, the "Dirty Priest" archetype uses a 1-mana card called "Potion of Madness," whose effect is: take control of an enemy minion with attack ≤ 2.

There is also a 4-mana card called "Shadow Madness," whose effect is: take control of an enemy minion with attack ≤ 3.

There is another 1-mana card called "Shrink Potion," whose effect is: reduce the attack of all enemy minions by 3.

You have "PY" (pinyin) the Hearthstone GM, so you now have unlimited copies of these three cards. However, the GM told you that "Shrink Potion" is harder to create. To be considerate to the GM, you must kill the opponent while using the minimum number of Shrink Potions.

Your opponent currently has n minions on board, with attack values k_i.

Your opponent has m health.

Your task is to take control of enemy minions onto your side and attack the opponent with them. Each minion can attack at most once, and the damage it deals equals its remaining attack at the moment you take control. You need to burst the opponent down (reduce their health to 0 or below).

Input Format

• The first line contains two integers n and m, separated by a space, representing the number of enemy minions and the opponent’s health.
• The second line contains n integers, separated by spaces, representing the attack values k_i of each enemy minion.

Output Format

• If it is possible to burst the opponent down, output one line with two integers: the minimum number of Shrink Potions used and the total mana crystals spent in that case, separated by a space. If there are multiple optimal answers with the same minimum number of Shrink Potions, output the one with the minimum mana crystals spent.
• Otherwise, output Human Cannot Win Dog (without quotes).

3 5
1 2 3 

0 5

8 8
10 20 30 40 50 60 70 80

16 23

8 80
10 20 30 40 50 60 70 80

Human Cannot Win Dog

Hint

Sample explanation 1:

• The enemy has 3 minions on board, and the opponent has 5 health.
• Take control of the 3-attack minion and the 2-attack minion, spending 0 Shrink Potions and 5 mana crystals (one Potion of Madness and one Shadow Madness, 1 + 4 = 5). The damage is enough to kill the opponent.

Sample explanation 2:

• Use 16 Shrink Potions (for each minion below, the first parenthesis is the attack when taken, and the second parenthesis is the total number of Shrink Potions used at that moment).
• Taking minions with original attacks 10 (1) (3), 20 (2) (6), 30 (3) (9), 50 (2) (16) deals a total of 8 damage, exactly lethal.

Subtasks:

• Easy: Guaranteed 0 < n ≤ 10, and no Shadow Madness or Shrink Potion is needed. 20%.
• Normal: Guaranteed 0 < n ≤ 10, and no Shrink Potion is needed. 20%.
• Hard: Guaranteed 0 < n ≤ 10. 30%.
• Extra: Guaranteed 0 ≤ n ≤ 5,000,000, maximum attack < 30,000. 30%.

Constraints:

• $0 < n \le 5{,}000{,}000$
• $0 < k_i \le 30{,}000$
• $0 \le m \le 5{,}000{,}000$ (6 zeros).

Translated by ChatGPT 5