Костя играет в компьютерную игру Cookie Clicker, основная цель которой — накопление запасов печенья. Получать печенья можно с помощью различных строений: можно просто кликать по специальному полю на экране, получая печенья за клики, можно купить фабрику печеньев, алхимическую лабораторию, машину времени, и все это будет приносить много-много печеньев.
В начале игры (момент времени 0) у Кости есть 0 печеньев и ни одного строения. На его выбор доступно n строений: i-ое строение стоит ci печеньев и в конце каждой секунды приносит vi печеньев. Кроме того, чтобы играть было еще интереснее, Костя решил поставить себе ограничение: в каждый момент времени он будет использовать только одно строение. Разумеется, он может по своему усмотрению менять активное строение каждую секунду.
Важно, что в версии игры, в которую играет Костя, покупать новые строения и менять активное строение можно только в моменты времени, кратные одной секунде. В один момент времени Костя может купить новое строение и тут же начать его использовать. Если Костя начал использовать строение в момент времени t, то первую прибыль оно сможет принести лишь в момент времени t + 1.
Костя хочет заработать не менее s печеньев как можно быстрее. Определите, за сколько секунд он сможет это сделать.
Выходные данные
Выведите единственное целое число — минимальное количество секунд, за которое Костя сможет заработать не менее s печеньев. Гарантируется, что он может это сделать.