被遗忘的计划

1000ms

524288K

Description:

在比特超市有 $$$n$$$ 种商品，依次编号为 $$$1$$$ 到 $$$n$$$，购买一件第 $$$i$$$ 种商品的价格为 $$$i$$$ 元，其价值为 $$$v_i$$$。由于备货充足，每种商品都可以购买任意非负整数件。

小Q计划购买恰好 $$$k$$$ ($$$1\leq k\leq 10^9$$$) 件商品，并计算出了 $$$f_0,f_1,f_2,\dots,f_{n-1}$$$，其中 $$$f_i$$$ 表示购买 $$$k$$$ 件商品且商品价格之和对 $$$n$$$ 取模的余数恰好为 $$$i$$$ 的所有方案中商品价值之和的最大可能值。

一天过去之后，健忘的小Q忘记了昨天做的购物计划中到底要买多少件物品，请写一个程序根据小Q的回忆找到 $$$k$$$ 的值。

Input:

第一行包含一个正整数 $$$n$$$ ($$$1\leq n\leq 1\,000$$$)，表示商品的种类数。

第二行包含 $$$n$$$ 个整数 $$$v_1,v_2,\dots,v_n$$$ ($$$1\leq |v_i|\leq 10^9$$$)，依次表示每种商品的价值。

第三行包含 $$$n$$$ 个整数 $$$f_0,f_1,\dots,f_{n-1}$$$ ($$$-10^{18}\leq f_i\leq 10^{18}$$$)，表示小Q回忆出来的 $$$f$$$ 的每一项的值。

Output:

输出一行一个整数 $$$k$$$ ($$$1\leq k\leq 10^9$$$)，即 $$$k$$$ 的取值，若有多个合法的 $$$k$$$，输出任意一个。如果小Q回忆有误，即在 $$$[1,10^9]$$$ 内找不到对应的 $$$k$$$，请输出"-1"。

Sample Input:

3
1 2 3
6 4 5

Sample Output:

Sample Input:

3
1 2 3
-1 -2 -3

Sample Output:

-1

Info

Provider CodeForces Gym

Origin 2021年中国大学生程序设计竞赛女生专场

Code GYM103389E