Minimum Cost to Achieve Display Strategies

In this problem, Xiao Piqiu is a university student and a fan of the game League of Legends. However, his skill level is low and he is teased by netizens as a "primary school student". To prove himself, Xiao Piqiu decides to buy skins for his heroes. He only plays N specific heroes. The i-th hero has \(K_i\) available skins, each costing \(C_i\) Q coins.

After buying some skins, Xiao Piqiu will showcase his collection to his classmates as follows: for every hero for which he has bought at least one skin, he picks one skin arbitrarily to show. Hence, if for example he buys skins for some heroes such that for each hero the number of skins he owns is \(x_i\) (with \(1\le x_i\le K_i\)), then the total number of different display strategies is the product \(\prod x_i\) over all heroes he selected.

He wants his display strategies to be at least \(M\) in number. In order to achieve this, he may choose a subset of heroes and for each chosen hero decide how many skins to buy (at least one and at most \(K_i\) for the hero). Note that he does not buy skins for heroes that do not have any available skins (i.e. when \(K_i=0\)).

Your task is to determine the minimum total cost required so that there is a way to choose (for one or more heroes) numbers \(x_i\) such that

[ \prod_{i \in S} x_i \ge M ]

where \(S\) is the set of heroes for which skins are bought. The cost paid for hero \(i\) is \(x_i \times C_i\). If it is impossible to obtain at least \(M\) strategies, output -1.

Note: For any multiplication result that reaches or exceeds \(M\), you can treat it as \(M\) (i.e. cap the product at \(M\) during calculations) since you only need to meet the threshold.

inputFormat

The first line contains two integers \(N\) and \(M\) (1 \(\leq\) N \(\leq\) 100, and 1 \(\leq M \leq 10^9\) possibly, though constraints may vary).

Then \(N\) lines follow. The \(i\)-th line contains two integers \(K_i\) and \(C_i\), where \(K_i\) (0 \(\le K_i \le 100\)) denotes the number of skins available for the \(i\)-th hero and \(C_i\) (1 \(\le C_i \le 10^9\)) denotes the cost per skin for that hero.

If a hero has \(K_i = 0\), it means no skins are available and that hero cannot be chosen.

outputFormat

Output a single integer -- the minimum total cost required to have at least \(M\) different display strategies, or -1 if it is impossible.

sample

5 24
0 10
0 10
3 3
2 2
4 1

17