Петя и его друзья собираются отпраздновать успешное окончание учебного года. Для этого они решили приобрести $$$n$$$ упаковок апельсинового сока и $$$m$$$ упаковок яблочного сока и выделили на эти цели $$$s$$$ рублей.
Одна упаковка любого сока стоит $$$r$$$ рублей. Однако можно приобретать сок коробками. Одна коробка содержит $$$k$$$ упаковок сока одного вида и стоит $$$p$$$ рублей (известно, что $$$k \cdot r \gt p$$$).
Друзья хотят приобрести как можно больше упаковок сока на имеющиеся деньги, но так, чтобы при этом было не менее $$$n$$$ упаковок апельсинового сока и не менее $$$m$$$ упаковок яблочного.
Сколько упаковок сока смогут приобрести друзья при таком условии?
В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$ — необходимое количество упаковок апельсинового сока.
Во второй строке содержится целое число $$$m$$$ $$$(1 \le m \le 5 \cdot 10^5)$$$ — необходимое количество упаковок яблочного сока.
В третьей строке содержится целое число $$$r$$$ $$$(1 \le r \le 1000)$$$ — цена одной упаковки сока (любого вида).
В четвёртой строке содержится целое число $$$k$$$ $$$(2 \le k \le 10^6)$$$ — количество упаковок сока в коробке.
В пятой строке содержится целое число $$$p$$$ $$$(1 \le p \lt k \cdot r)$$$ — цена коробки, содержащей $$$k$$$ упаковок сока.
В шестой строке содержится целое число $$$s$$$ $$$(1 \le s \le 10^9)$$$ — количество денег, выделенных на покупку сока.
Выведите целое число — максимально возможное суммарное количество упаковок сока, которые получится приобрести.
Если невозможно приобрести сок, соблюдая описанные условия, выведите $$$-1$$$.
Решения, правильно работающие, когда хотя бы одна из величин $$$n$$$ или $$$m$$$ делится на $$$k$$$ нацело, будут оцениваться в $$$25$$$ баллов.
878053701400
18
878052251200
25
878053751100
-1
В первом примере из условия нужно купить $$$8$$$ упаковок апельсинового сока и $$$7$$$ упаковок яблочного сока. Одна упаковка стоит $$$80$$$ рублей, а коробка из $$$5$$$ упаковок — $$$370$$$ рублей. На $$$1110$$$ рублей можно купить $$$3$$$ коробки сока, например, две коробки апельсинового и одну коробку яблочного. Останется $$$1400-3\cdot 370=290$$$ рублей: $$$240$$$ рублей хватит на $$$3$$$ упаковки яблочного сока (или $$$2$$$ упаковки яблочного и $$$1$$$ — апельсинового), $$$50$$$ рублей останется. Условия будут выполнены, всего будет приобретено $$$3\cdot5 + 3=18$$$ упаковок сока.
Во втором примере на $$$1200$$$ рублей можно приобрести $$$5$$$ коробок сока по $$$225$$$ рублей. Если взять три коробки апельсинового сока и две коробки яблочного, то условия будут выполнены. Останется $$$1200 - 5 \cdot 225= 75$$$ рублей, на которые ничего нельзя купить.
В третьем примере на $$$1100$$$ рублей можно купить $$$2$$$ коробки сока по $$$375$$$ рублей: коробку апельсинового и коробку яблочного. Останется $$$1100 - 2 \cdot 375=350$$$ рублей, на которые нужно купить ещё три упаковки апельсинового и две упаковки яблочного сока. При стоимости упаковки в $$$80$$$ рублей это сделать нельзя.
