Time-3 - I'm Not Blind!

2 secs 1024 MB
matcharate12's icon matcharate12

AC報酬: 55 ラテコイン

Story

今年も、夏祭りの季節がやってきました。
Targetrate君はその祭りに行きました。祭りには懐かしの屋台があったり、屋台の食べ物が売られていました。今日も活気がある祭りです。

その中でも一番目玉なのは「射的」です。Targetrate君は屋台の食べ物を食べたそ~に見つめながらそのゲームに参加しました。
しかしこのゲームはかなり難易度が高いという噂を聞きました。その理由は、射撃の的が動くのです。止まってる的でさえあんな難しいのに、なぜ回転させたのでしょうかね...
何はともあれ、ではさっそくやってみましょう!!

...結果は、Targetrate君だけが知っています。Targetrate君の友達であるmatcharate君も、流石に得点は知りたいと思っています。
そう思ってるうち、Targetrate君は独り言をつぶやきました。

「いや~... NN 枚の的だけ外しちゃった。。。もう一回やる!!!」

全く。負けず嫌いですねこの人は。
と、思っているとTargetrate君はこう言ってきました。

「じゃあ、今から言う情報だけで自分が何点とったか当ててみて!!そしたら報酬あげるわ!!」

なぜ報酬をくれるんでしょうか...?

問題

NN 枚の的があります。それぞれの的には 1,2,...,N1,2,...,N と番号づけられています。最初、的 i (1iN)i\ (1\le i\le N) には数値 AiA_i が書かれています。

その後、tt 秒後にすべての的がランダムな位置に移動します。このとき同じ位置に 22 つ以上の的が来ることはありません。
具体的には ii 番目の的の位置 pip_i として、数列 (p1,p2,...,pN)(p_1,p_2,...,p_N)11 以上 NN 以下の整数からなる順列 (1,2,...,N)(1,2,...,N) に等しいか、それを並び替えたものに等しくなります。

matcharate君はTargetrate君の得点を知りたいと思っています。
Targetrate君の独り言によると、左から B1,B2,...,BMB_1,B_2,...,B_M 番目の的を撃ち落とすことができなかったようです。それ以外は全て撃ち落とすことができたようです。

Targetrate君の得点は撃ち落とせた的に書かれた数字の合計となります。
すなわち A=(A1,A2,...,AN)A=(A_1,A_2,...,A_N) を並び替えたもの C=(C1,C2,...,CN)C=(C_1,C_2,...,C_N) に対して、得点は CB1+CB2+...+CBNMC_{B_1'}+C_{B_2'}+...+C_{B_{N-M}'} となります。ただし BB' において j=1,2,...,M,k=1,2,...,NMj=1,2,...,M,k=1,2,...,N-M に対し BjBkB_j\ne B_k' です。

-Mission-
十分な時間この射的で遊んだ時、Targetrate君が得た可能性がある得点は何通りあるか。報告せよ。

入力

入力は以下の形式で与えられる。

NNMM
A1A_1A2A_2\dotsANA_N
B1B_1B2B_2\dotsBMB_M

制約

  • 1N81\le N\le 8
  • 0MN10\le M\le N-1
  • 1Ai5×1081\le A_i\le 5\times 10^8
  • 1BjN1\le B_j\le N
  • B1,B2,...,BMB_1,B_2,...,B_M はすべて異なる
  • 入力はすべて整数

出力

答えを出力せよ。

入出力例

入力例1
3 1
1 2 3
1
出力例1
3

順列 (1,2,3)(1,2,3) を並び替えた数列 P=(P1,P2,P3)P=(P_1,P_2,P_3) とすると11 番目だけ撃ち落とせなかったので P1=0P_1=0 となります。
よって考えられるのは次の 33 通りです。

  • 1,2,31,2,3 番目のこの順で的があったとき、得点は A1+A2+A3=0+2+3=5A_1+A_2+A_3=0+2+3=5 です。
  • 2,3,12,3,1 番目のこの順で的があったとき、得点は A2+A3+A1=0+3+1=4A_2+A_3+A_1=0+3+1=4 です。
  • 3,2,13,2,1 番目のこの順で的があったとき、得点は A3+A2+A1=0+2+1=3A_3+A_2+A_1=0+2+1=3 です。
入力例2
3 1
1 1 1
1
出力例2
1

どのように的が動いたとしても、考えられる得点は 1+1=21+1=2 のみです。

入力例3
3 0
1 2 3

出力例3
1

全ての的を撃ち落としました。matcharate君は射撃の天才なのかもしれません。

入力例4
7 3
6 1 9 3 7 1 8
2 4 5
出力例4
18

提出


Go (1.21)