思考题 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 pow_i - 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 px and the object's power is py. we call the object absorbable if there exists an integer i(1\leq i\leq k,k is given) so that py=ipx+1.
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 px:=py.
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(3=2\times1+1) then now slime's pow=3
Absorb Monster 3(100=3\times33+1) then now slime's pow=100
Absorb Monster 2(301=100\times3+1) then now slime's pow=301
Way 2
Absorb Monster 1(3=2\times1+1) then now slime's pow=3
Absorb Monster 2(301=3\times100+1) then now slime's pow=301
Way 3
Absorb Monster 2(301=2\times150+1) 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 O(n* \sqrt {n}*log(n))