思考题 of math again

Slime Legend II

In the world of fantasy, there lives N+1 types of monsters indexed from 0 to N. Each monster can be represented by an integer - their power. And specially, type 0 is SLIME. Slime has a special ability to "absorb" his enemy. Let's talk about it in detail:

Assume now the slime's power is and the object's power is . we call the object absorbable if there exists an integer i(,k is given) so that .

If a monster is alive and it's absorbable, the slime can absorb the monster. To do so, the monster's ability will be copied and the monster will be set dead. That's .

What's the maximum monster can be absorbed by the little slime?

Example

Input
Pow={3,301,100}
Pow_Of_Slime=2
k=300
Output
3
Explain
There are several ways:

Way 1
Absorb Monster 1() then now slime's pow=3
Absorb Monster 3() then now slime's pow=100
Absorb Monster 2() then now slime's pow=301

Way 2
Absorb Monster 1() then now slime's pow=3
Absorb Monster 2() then now slime's pow=301

Way 3
Absorb Monster 2() then now slime's pow=301

It's obvious that the first way is the best.

Constriants

Subtask1(1%):K=1
Subtask2(30%):K=1e9
Subtask3(40%):N=1000
Subtask4(4%):K=2
Subtask5(5%):K=3
Subtask6(5%):K<=1e5
For all data, 1<=K<=1e9,1<=N<=1e5 holds. power is at most 1e9.

Solution By Monkey King

Problem can be solved by DP backwards in
fantasy