Background

大哲同学在某种超自然的力量下获得了"拍口袋"的魔法
本题为升级版，建议先通过拍口袋

Description

大哲的口袋里现在有m块饼干和0元，现在他有k次施展"拍口袋"魔法的机会
这个魔法是这样的，每次施展大哲都可以任选下列三个事件之一发生:
1.口袋里的饼干增加1块
2.把口袋里的a块饼干换成x元
3.把y元换成b块饼干

一开始，大哲的口袋里是没有钱的。现在大哲想要知道他最多可以让口袋里的饼干有多少块

Format

Input

输入六个整数m,k,a,b,x,y（含义见题目描述）

Output

输出一个整数，表示大哲在施展k次魔法后最多口袋里可能有多少块饼干

Sample 1

Input

5 3 2 4 1 1

Output

8

第1次拍口袋把2块饼干换成1元，现在有3块饼干1元
第2次拍口袋增加口袋里的饼干数，现在有4块饼干1元
第3次拍口袋把1元换成4块饼干，现在有8块饼干

Sample 2

Input

6 8 1 2 2 3

Output

14

Sample 3

Input

2 3 2 6 5 3

Output

7

Data range

对于100%的数据点，满足 0 < m,k,a,b ≤ 10^5，0 < x,y ≤ 10

Limitation

1s, 128MB for each test case.