# Bribe The Friend Again!

After losing a lot of money in Bribe The Friend, Andrei decides to play it safe. Kostya selects a number from 1 to 144, and Andrei is allowed to choose a single subset of the set {$$1,2,...144$$}. Kostya is asked whether his chosen number belongs to that subset (being a very nice boy, Kostya is always truthful). If Kostya answers yes, Andrei must give him two pounds, if he answers no- one pound. Find the minimum sum of money Andrei must pay before being certain of the number.

×