import Data.Ratio
import qualified Data.Map as M
main=do{([_,m,n]:s)<-map(map read.words).lines<$>getContents;print$M.findWithDefault(-1)(m%n)$M.mapKeysWith min(uncurry(%))$M.deleteMin.foldl(\h[a,b,c]->M.unionWith min h$M.mapKeys(\(k,l)->(k+a,l+b))$M.map(+c)h)(M.singleton(0,0)0)$s}