思考题 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))$