Tom the lazy cat wants to catch some mice that live near him, but he is too lazy to ever move away from his favorite chair. Fortunately, he has several hats which can be thrown to catch mice. If there is an uncaught mouse no further than d feet from Tom, he can throw one of his hats and catch that mouse (throwing a hat takes no time). Tom is a very clever cat, so he never misses, but he must have a rest after each throw and he cannot use the same hat more than once.
At time 0, the i-th mouse is pos[i] feet away from Tom, and is running away from Tom at the speed of speed[i] feet per second. So, after k seconds, the i-th mouse will be (pos[i] + k * speed[i]) feet away from Tom.
Tom is given n hats, numbered 0 through n-1, and he may throw them in any order. He must wait rest[i] seconds after throwing hat number i (he cannot throw any more hats during this time).
You are given an int d, the maximum distance a hat can be thrown (this distance is the same for all hats). Return the maximal number of mice he'll be able to catch.
|