P12927 [POI 2022/2023 R2] 车厢 / Wagony

翻译来自于 [LibreOJ](https://loj.ac/p/5022)。

**题目译自 [XXX Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi30-2/dashboard/) [Wagony](https://szkopul.edu.pl/problemset/problem/UtJx9fM6UT2oxXFenSPjiz5C/statement/)** 在一维铁轨上停放着 $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$ 个车厢合并成一个列车的最小成本。

**样例 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$。 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 100000$ | $21$ | | $2$ | $d \leq 300$ | $46$ | | $3$ | 无附加限制 | $33$ |