题目描述

地面上有一排长度为 $n$ 的格子 $1-n$ ，每个格子上都有一个数 $x_i$ ，开始时你在位置 $0$ ，每次你可以向前跳 $1\sim2$ 格，然后取走格子上的数，直到跳到位置 $n+1$ 。

取走的数的和就是你的得分，现在你想知道你可能的最大得分是多少。

输入

一行四个整数 $n,A,B,C(n≤100000,\ 0≤A,B,C≤10000)$，其中 $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

来源

动态规划