Dice Battle Game

A camp director has designed a dice battle game for two teams. One team attacks and the other defends. Each team has a base with some number of people.

In each round, the attacking team sends people to attack the defending base, and the defending team sends people to defend. The number of people sent is fixed by these rules:

1. The attacking team must leave at least one person in its own base. If it has 3 people, it can send at most 2 attackers. The defending team may send everyone because it is defending its own base.
2. Each team can send at most 3 people in one round.
3. Each team must send as many people as it can under the rules above.

Equivalently, if the attacking team currently has A people and the defending team has D people, the attacking team sends min(3, A - 1) people and the defending team sends min(3, D) people.

All people sent by both teams roll one six-sided die. Sort each team's rolls in descending order. Compare the highest attacking roll with the highest defending roll, the second-highest with the second-highest, and so on for as many pairs as both teams have. In each comparison, the person with the lower roll dies. If the two rolls are equal, the defender wins that comparison and the attacker dies.

After the comparisons, all surviving participants return to their own bases, and the next round begins. If the attacking team can no longer attack, for example because only one attacker remains, the defending team wins. If all defenders die, the attacking team wins.

Given the initial number of defenders, find the minimum initial number of attackers needed so that the attacking team wins with probability at least 50%.

The first line contains the number of defenders N (1 <= N <= 1000).

Print the minimum number of attackers required.