You are in position (0, 0) of a coordinate plane. You want to determine if you can reach point (x, y). There are n different types of steps that you can make. Step type i is represented by two non-negative integers a_i, b_i which means that a step of type i moves you a_i steps to the right and b_i steps up.

How to determine if it is possible to reach point (x, y) using only those type of steps? You are allowed to use a type of step multiple times but you can't do half of a step.

Can this problem be solved with complexity better than O(x * y * n)?