we can denote optimal solution of (p1,t1,p2,t2) f(t1,t2).notice if two pets start at same time ,then it will be conflict in t==0,so one of the pet must move at least 1 seconds to right,then we can find next conflict position. there are two kinds of choose: move first pet 1 seconds to right,then next conflit position will be solution of p2*x2-p1*y2==1 (first pet will be feed y2 times,and second will be feed x2 times)then next state will be f(t1-y2,t2-x2). increment of time is p2*x2. second choice is :move second pet 1 seconds to right,then equation will be p1*x1-p2*y1==1 next state will be f(t1-x1,t2-y1),increment of time is p1*x1.

so we can get recursion formula: f(t1,t2)=min(f(t1-x1,t2-y1)+p1*x1),f(t1-y2,t2-x2)+p2*x2)) notice :f(0,0)=1;

then we can get further observision for state (t1,t2) we must choose k1 pair of (x1,y1) transition,and k2 pair of (x2,y2) transition,then we can get

k1*x1+k2*y2>=t1

k1*y1+k2*x2>=t2

min(p1*k1*x1+p2*k2*x2)

(x1>=0,y1>=0,x2>=0,y2>=0)

notice: k1*x1 and k2*x2 must be integer, other not necessary.

this will be solved by linear programming. cutting plane algorithm will be work in O(1)