Президент одной маленькой, но очень гордой страны вдруг узнал, что на дворе двадцать первый век, и на лошадях ездить уже не модно. Однако, как выяснилось, нефти в стране нет, а без бензина автомобили ездить не умеют. Так что придется закупать нефть в других странах.

Исследование внешнего рынка показало, что в мире есть n стран, экспортирующих нефть. При этом i-е государство продает баррель нефти либо за a_i долларов, либо за b_i евро.

У президента есть a долларов и b евро. Главный бухгалтер утверждает, что если попытаться купить нефть у одного государства и за доллары, и за евро, то бюрократия может надолго отложить покупку, чего президент, разумеется, не хочет.

Помогите президенту в таких непростых условиях узнать, сколько баррелей нефти он сможет купить.