Костя играет в компьютерную игру Cookie Clicker, основная цель которой — накопление запасов печенья. Получать печенья можно с помощью различных строений: можно просто кликать по специальному полю на экране, получая печенья за клики, можно купить фабрику печеньев, алхимическую лабораторию, машину времени, и все это будет приносить много-много печеньев.

В начале игры (момент времени 0) у Кости есть 0 печеньев и ни одного строения. На его выбор доступно n строений: i-ое строение стоит c_i печеньев и в конце каждой секунды приносит v_i печеньев. Кроме того, чтобы играть было еще интереснее, Костя решил поставить себе ограничение: в каждый момент времени он будет использовать только одно строение. Разумеется, он может по своему усмотрению менять активное строение каждую секунду.

Важно, что в версии игры, в которую играет Костя, покупать новые строения и менять активное строение можно только в моменты времени, кратные одной секунде. В один момент времени Костя может купить новое строение и тут же начать его использовать. Если Костя начал использовать строение в момент времени t, то первую прибыль оно сможет принести лишь в момент времени t + 1.

Костя хочет заработать не менее s печеньев как можно быстрее. Определите, за сколько секунд он сможет это сделать.