说明

地面上有一排长度为$n$的格子1-$n$，每个格子上都有一个数$x_i$，开始时你在位置0，每次你可以向前跳1-2格，然后取走格子上的数，直到跳到位置$n$+1。取走的数的和就是你的得分，现在你想知道你可能的最大得分是多少。

输入格式

一行四个整数$n,A,B,C$，其中$n$表示格子的数量。$x[i]$由如下方式生成：

for (int i = 1; i ≤  n; i++){
  int tmp = ((long long)A * i * i + B * i + C) % 20000;
  x[i] = tmp - 10000;
}

输出格式

一行一个整数ans表示可能的最大得分。

样例

3 1 1 1

-9993

50 60 70 80 90

47070

数据范围

$n≤100000,0≤A,B,C≤10000$