在一条一维轨道上停放着 $n$ 节车厢。最初，没有任何两节车厢是连接在一起的。在每一步操作中，你可以将两组相邻的已连接车厢合并，前提是这两组车厢的数量之差不超过 $d$。执行此类合并所需的时间取决于被合并组中车厢的数量。你的任务是将所有车厢合并成一个包含 $n$ 节车厢的列车。

将一组包含 $w$ 节车厢的组与一组包含 $v$ 节车厢的组进行合并（前提是 $|w - v| \le d$）的代价由函数 $(aw + bv) \pmod{1001}$ 给出。

输入格式

输入仅一行，包含四个正整数 $n, d, a$ 和 $b$ ($1 \le n \le 10^{16}, 1 \le d, a, b \le 1000$)。

输出格式

输出仅一行，包含一个整数，表示将所有 $n$ 节车厢合并成一列火车的最小代价。

样例

输入格式 1

5 1 1 1

输出格式 1

12

说明

将第一节车厢与第二节合并（代价 2），第三节与第四节合并（代价 2），然后与第五节合并（代价 3），最后将两组已形成的组进行合并（代价 5）。

测试用例

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

评分