CF734C Anton and Making Potions

Anton 正在玩一个非常有趣的电脑游戏，但现在他卡在了某一关。为了进入下一关，他必须制作 $n$ 瓶药水。 Anton 有一个特殊的水壶，每 $x$ 秒可以制作一瓶药水。此外，他还掌握了两类可以加快药水制作速度的法术。 1. 第一类法术可以加速每瓶药水的制作时间。共有 $m$ 个这类法术，第 $i$ 个法术需要消耗 $b_i$ 点法力值，可以将每个药水的制作时间改为 $a_i$ 秒（原本是 $x$ 秒）。 2. 第二类法术可以立即完成若干瓶药水的制作。共有 $k$ 个这类法术，第 $i$ 个法术需要消耗 $d_i$ 点法力值，可以立刻制作 $c_i$ 瓶药水。 Anton 最多只能选择使用一类第一种法术和一种第二种法术，并且总共消耗的法力值不能超过 $s$。所有法术都会在Anton开始制作药水之前瞬间生效。 Anton 希望能最快进入下一关，因此他关心完成至少 $n$ 瓶药水所需的最短时间。

输入的第一行包含三个整数 $n$、$m$、$k$（$1\le n\le 2\times 10^9, 1\le m,k\le 2\times 10^5$），分别表示 Anton 需要制作的药水数、第一类法术的数量和第二类法术的数量。 第二行包含两个整数 $x$ 和 $s$（$2\le x\le 2\times 10^9, 1\le s\le 2\times 10^9$），分别表示初始制作一瓶药水所需的秒数和Anton可用的总法力值。 第三行包含 $m$ 个整数 $a_i$（$1\le a_i < x$），表示如果使用第 $i$ 个第一类法术，则每瓶药水的制作时间将变为 $a_i$ 秒。 第四行包含 $m$ 个整数 $b_i$（$1\le b_i \le 2 \times 10^9$），表示使用第 $i$ 个第一类法术所需的法力值。 第五行包含 $k$ 个整数 $c_i$（$1\le c_i \le n$），表示如果使用第 $i$ 个第二类法术，能够立即制作 $c_i$ 瓶药水。保证 $c_i$ 非递减，即 $c_i \le c_j$ 当 $i < j$。 第六行包含 $k$ 个整数 $d_i$（$1\le d_i \le 2\times 10^9$），表示使用第 $i$ 个第二类法术所需的法力值。保证 $d_i$ 非递减，即 $d_i \le d_j$ 当 $i < j$。

输出一个整数，表示完成制作 $n$ 瓶药水所需的最短时间。

在第一个样例中，最优解是使用第二个第一类法术，消耗 $10$ 点法力，使每瓶药水的制作时间变为 $4$ 秒。同时使用第二个第二类法术，消耗 $80$ 点法力，直接制作 $15$ 瓶药水。共消耗法力值 $10+80=90$，总制作时间为 $4 \times 5 = 20$ 秒（$15$ 瓶药水已瞬间完成，剩下 $5$ 瓶每瓶需 $4$ 秒）。 在第二个样例中，Anton 不能使用任何法术，所以他只能制作 $20$ 瓶药水，每瓶耗时 $10$ 秒，总共 $20 \times 10 = 200$ 秒。 由 ChatGPT 5 翻译