問題文
数列 A=(A1,A2,…,AN)、数列 P=(P1,P2,…,PQ)、数列 J=(J1,J2,…,JQ) が与えられます。
各 i (1≤i≤N) について以下のどちらかの条件を満たす数列を 良い数列 と言います。
- 数列の i 項目が +Ai と等しい。
- 数列の i 項目が −Ai と等しい。
また、ある良い数列の 美しさ を以下の条件を満たす j (1≤j≤Q) の個数とします。
- 良い数列を B とした時、B1+B2+⋯+BPj を 7 で割った余りが Jj と等しい。
あり得る良い数列の美しさの最大値を求めてください。
制約
- 1≤N≤2×105
- 1≤Q≤N
- 0≤Ai≤109
- 1≤P1<P2<⋯<PQ≤N
- 0≤Jj<7
- 入力はすべて整数
入力
N Q
A1 A2 ... AN
P1 P2 ... PQ
J1 J2 ... JQ
出力
あり得る良い数列の美しさの最大値を出力してください。
サンプル
入力1
4 4
1 3 2 5
1 2 3 4
5 1 5 0
美しさが 2 である良い数列として (−1,−3,+2,−5) が考えられます。
左から累積和を取ると (6,3,5,0) となり、J と 2 つの要素が一致している (美しさが 2 である) ことが分かります。
これより美しさが大きい数列は存在しないため、2 を出力します。
入力2
4 3
6 3 1 0
1 2 3
1 6 4
美しさが 2 である良い数列は例えば (−6,−3,−1,−0) です。
入力3
14 8
4 4 2 6 0 1 3 4 5 6 2 2 6 2
1 2 4 6 7 8 9 12
6 5 1 0 5 3 6 3