题目描述

Alice has recently become fascinated with Plants vs. Zombies (Sunflower Edition). There are two types of sunflowers: the $i$-th type requires $p_i$ sun to plant and generates $q_i$ sun per round. Initially, you have $s$ sun. At the beginning of each round, you can buy and plant each type of sunflower at most once. At the end of each round, you will get all the sun generated by your sunflowers planted in this and previous rounds. Assuming you can plant an unlimited number of sunflowers, calculate the maximum amount of sun you can have after $n$ rounds.官方中文

输入格式

The first line contains two integers $s$ and $n$ ($1 \leq s, n \leq 2 \times 10^7$), representing the initial amount of sun you have and the number of rounds the game will be played. The second line contains two integers $p_1$ and $q_1$ ($1 \leq p_1, q_1 \leq 1023$), describing the attributes of the first type of sunflower. The third line contains two integers $p_2$ and $q_2$ ($1 \leq p_2, q_2 \leq 1023$), describing the attributes of the second type of sunflower.官方中文

输出格式

Output a single integer, which is the maximum amount of sun you can have after $n$ rounds.官方中文

说明

In the first sample test case, Alice starts with $75$ sun and has $3$ rounds to plant sunflowers. Here is the optimal strategy:In the first round, spend $50 + 25 = 75$ sun to plant both types of sunflowers. At the end of the round, $25 + 15 = 40$ sun would be generated.In the second round, spend $25$ sun to plant the second type of sunflower and keep $40 - 25 = 15$ sun. At the end of the round, $25 + 15 + 15 = 55$ sun would be generated, and your sun would increase to $15 + 55 = 70$.In the third round, do not buy new sunflowers. After collecting $55$ sun for this round, you would have $70 + 55 = 125$ sun.官方中文