Монокарп решил купить игрушки на новогоднюю елку. В магазине есть игрушки трех цветов — красные, желтые и синие. Известно, что в магазине есть неограниченное количество игрушек каждого цвета.
Одна игрушка красного цвета стоит $$$r$$$ бурлей, одна игрушка желтого цвета стоит $$$y$$$ бурлей, а одна игрушка синего цвета стоит $$$b$$$ бурлей.
У Монокарпа есть всего $$$n$$$ бурлей, и он хочет купить как можно больше игрушек. При этом он считает, что елка будет красиво украшена, если количества игрушек каждого цвета, которые он купит, отличаются друг от друга не более, чем на единицу. Более формально, если Монокарп купит $$$cnt_r$$$ игрушек красного цвета, $$$cnt_y$$$ игрушек желтого цвета и $$$cnt_b$$$ игрушек синего цвета, то должны выполняться неравенства: $$$|cnt_r - cnt_y| \le 1$$$, $$$|cnt_r - cnt_b| \le 1$$$, $$$|cnt_y - cnt_b| \le 1$$$.
Определите максимальное суммарное количество игрушек, которые Монокарп может купить в магазине, при условии, что количества купленных игрушек каждого цвета должны отличаться не более, чем на единицу.
В первой строке задано целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество бурлей, которое есть у Монокарпа.
Во второй строке задано целое число $$$r$$$ ($$$1 \le r \le n$$$) — стоимость в бурлях одной игрушки красного цвета.
В третьей строке задано целое число $$$y$$$ ($$$1 \le y \le n$$$) — стоимость в бурлях одной игрушки желтого цвета.
В четвертой строке задано целое число $$$b$$$ ($$$1 \le b \le n$$$) — стоимость в бурлях одной игрушки синего цвета.
Выведите максимальное суммарное количество игрушек, которые Монокарп может купить в магазине, при условии, что количества купленных игрушек каждого цвета должны отличаться не более, чем на единицу.
12 2 2 2
6
26 1 4 7
7
17 4 2 3
5
100 100 100 100
1
В первом примере Монокарп может купить по две игрушки каждого цвета, потратив на это все $$$12$$$ бурлей, которые у него есть. Таким образом, максимально Монокарп может купить $$$6$$$ игрушек.
Во втором примере Монокарп может купить $$$3$$$ игрушки красного цвета, $$$2$$$ игрушки желтого цвета и $$$2$$$ игрушки синего цвета, потратив на это $$$3 \cdot 1 + 2 \cdot 4 + 2 \cdot 7 = 25$$$ бурлей. Таким образом, максимально Монокарп может купить $$$7$$$ игрушек. При этом у Монокарпа останется $$$1$$$ бурль, но купить еще одну игрушку красного цвета он не может, так как в этом случае нарушится ограничение на количества купленных игрушек, описанное в условии.
В третьем примере Монокарп может купить $$$1$$$ игрушку красного цвета, $$$2$$$ игрушки желтого цвета и $$$2$$$ игрушки синего цвета, потратив на это $$$1 \cdot 4 + 2 \cdot 2 + 2 \cdot 3 = 14$$$ бурлей. Таким образом, максимально Монокарп может купить $$$5$$$ игрушек.
Название |
---|