E-炒鸡矿工_牛客练习赛75

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小 $\text{D}$ 最近在玩一款叫做炒鸡矿工的游戏。这个游戏的玩法建立在一个挖矿系统上。
我们认为游戏从第 $\text 0$ 分钟开始，每过 $\mathop p$ 分钟，炒鸡矿工可以完成一次挖矿，每次可以挖重量为 $\mathop c$ 的金矿，准确的说，在一次挖矿中，小 $\text{D}$ 会在第 $\mathop p$ 分钟末收获重量为 $\mathop c$ 的金矿。炒鸡矿工在开局后会不断地重复挖矿操作，不能休息。
金矿可以储存或用于升级挖矿系统。
开局时，挖矿系统的等级为 $\text 1$ 级。挖矿系统最多升到 $n+\text 1$ 级。升级操作不消耗时间，但只能在一次挖矿开始前进行。每次升级会从第 $\mathop i$ 级升级到第 $i+1(1\le i \le n)$ 级，需要花费重量为 $w_i$ 的金矿，可以使每次挖矿的重量增加 $v_i$ ，使每次挖矿的时间变成 $s_i$ 。由于升级不消耗时间，小 $\text{D}$ 可以在一瞬间多次升级。
开局时，小 $\text{D}$ 拥有重量为 $\mathop m$ 的金矿。他想知道，在开局后恰好 $\mathop t$ 分钟时，他最多能拥有的金矿重量是多少。

输入描述:

输入共行（或行）。
第一行包含个非负整数。
第二行包含个非负整数，第个数表示。
第三行包含个非负整数，第个数表示。
第四行包含个正整数，第个数表示。
若，则只有第一行。

输出描述:

输出共一行，包含一个非负整数，表示最多能拥有的金矿重量。

示例1

输入

复制

输出

复制

说明

下面给出一种可行的方案（同一行内相同颜色标记表示相关联的变化）：