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 time complexity better than *O*(*x* * *y* * *n*)?