题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 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

提示

样例 1 解释

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

附加样例

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

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