[ARC150F] Constant Sum Subsequence

有一个长度为 $n^2$ 的序列 $\{ a_i \}$ 以及一个整数 $sum$。 对于 $\forall i\in[1,n^2-n]$，这个序列满足 $a_i=a_{i+n}$，在本题中只给出 $n$ 个数 $\{ a_1,\dots,a_n\}$。 现在要求你找到一个最小的整数 $p$，使得所有满足 $\sum_{i} b_i=sum$ 的序列 $\{b_i\}$ 是 $\{a_1,\dots,a_p\}$ 的子序列。

[problemUrl]: https://atcoder.jp/contests/arc150/tasks/arc150_f 長さが $ N^2 $ の正整数列 $ A=(A_1,\ A_2,\ \dots,\ A_{N^2}) $ と正整数 $ S $ があります。この正整数列については正整数 $ i\ (1\leq\ i\ \leq\ N^2-N) $ に対し $ A_i=A_{i+N} $ が成り立ち、$ A_1,\ A_2,\ \dots,\ A_N $ のみが入力で与えられます。 総和が $ S $ であるような任意の正整数列 $ B $ が正整数列 $ (A_1,\ A_2,\ \dots,\ A_L) $ の（連続とは限らない）部分列となるような最小の整数 $ L $ を求めてください。 この問題の制約のもとでそのような $ L $ が $ 1 $ つ以上存在することが示せます。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ S $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを出力してください。

6 4
1 1 2 1 4 3

9

14 5
1 1 1 2 3 1 2 4 5 1 1 2 3 1

11

19 10
1 6 2 7 4 8 5 9 1 10 4 1 3 1 3 2 2 2 1

39

### 制約 - $ 1\ \leq\ N\ \leq\ 1.5\ \times\ 10^6 $ - $ 1\ \leq\ S\ \leq\ \min(N,2\ \times\ 10^5) $ - $ 1\ \leq\ A_i\ \leq\ S $ - 任意の正整数 $ x\ (1\leq\ x\ \leq\ S) $ について、$ (A_1,\ A_2,\ \dots,\ A_N) $ は $ x $ を $ 1 $ つ以上含む - 入力される値はすべて整数 ### Sample Explanation 1 $ B $ として考えるべきなのは $ B=(1,\ 1,\ 1,\ 1),\ (1,\ 1,\ 2),\ (1,\ 2,\ 1),\ (1,\ 3),\ (2,\ 1,\ 1),\ (2,\ 2),\ (3,\ 1),\ (4) $ です。 例えば $ L=8 $ とすると $ B=(2,\ 2) $ は $ (A_1,A_2,\ \dots,\ A_8)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1) $ の部分列となりません。 一方で $ L=9 $ とするとすべての $ B $ が $ (A_1,A_2,\ \dots,\ A_9)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1,\ 2) $ の部分列となります。