题目描述

题目译自 XXX Olimpiada Informatyczna – II etap Wagony

在一维铁轨上停放着 $n$ 个车厢，初始时各车厢互不连接。每次操作可将相邻的两组已连接车厢合并，前提是两组车厢数量差不超过 $d$。合并耗时取决于两组车厢数量。你的任务是将所有车厢合并成一个含 $n$ 个车厢的列车。

合并含 $w$ 个车厢的组与含 $v$ 个车厢的组（满足 $|w-v| \leq d$）的成本由奇特函数 $(a w + b v) \bmod 1001$ 计算。

输入格式

第一行包含四个正整数 $n$, $d$, $a$, $b$ $(1 \leq n \leq 10^{16}$, $1 \leq d, a, b \leq 1000)$，分别表示车厢总数、数量差上限和成本函数参数。

输出格式

输出一个整数，表示将 $n$ 个车厢合并成一个列车的最小成本。

样例

输入

5 1 1 1

输出

12

解释

我们将第一个车厢与第二个车厢连接（成本 $2$），第三个车厢与第四个车厢连接（成本 $2$），然后再与第五个车厢连接（成本 $3$），最后将两个形成的车厢组连接（成本 $5$）。

附加样例

• $n=10$, $d=3$, $a=2$, $b=3$。
• $n=10^5$, $d=1000$, $a=3$, $b=5$。
• $n=10^{16}$, $d=300$, $a=3$, $b=5$。

数据范围与提示

详细子任务附加限制及分值如下表所示。