005 - どろだんご

問題

ウジサト君はどろだんごを販売する会社を経営している。仕入れたどろだんごに土と水を塗り、美しいどろだんごに仕上げて販売している。

ウジサト君は、様々な粘度の土と、様々な純度の水に、土には1から$N$、水には1から$M$の番号を振って管理している。それらの中から、それぞれ数種類使ってどろだんごを作る。一つのどろだんごを完成させるまで、様々な土と水を選びそれらを順番に塗っていく。ただし、一度使った土や水を２回以上塗ることはできない。

どろだんごの品質は、大きさ、柔らかさ、美しさの３つの尺度により決まる。大きさ$s$、柔らかさ$h$、美しさ$b$のどろだんごに土か水を塗ると、その大きさ、柔らかさ、美しさは以下のようになる。

• 粘度$v$の土を塗ると、大きさと美しさがそれぞれ$v$、$h \times v$増える。柔らかさは変わらない。
• 純度$p$の水を塗ると、柔らかさと美しさがそれぞれ$p$、$s \times p$増える。大きさは変わらない。

ウジサト君は、常連客からどろだんごの美しさのバリエーションはどれくらいあるのかという質問を受けた。そこで、ウジサト君はどろだんごの美しさが何種類あるかを求めるプログラムを書くことにした。

土の種類と水の種類の数、それぞれの土の粘度と水の純度が与えられたとき、それらを使って作れるどろだんごの美しさが何種類あるかを求めるプログラムを作成せよ。ただし、仕入れたときのどろだんごの大きさ、柔らかさ、美しさはどれも1とし、仕入れたときのどろだんごの美しさも一つの種類とする。

入力

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

$N$ $M$
$v_1$ $v_2$ ... $v_N$
$p_1$ $p_2$ ... $p_M$

１行目に、土の種類の数$N$ ($1 \leq N \leq 10$)と水の種類の数$M$ ($1 \leq M \leq 10$)が与えられる。２行目に、$i$番目の種類の土の粘度$v_i$ ($1 \leq v_i \leq 100,000,000$)が整数で与えられる。３行目に、$i$番目の種類の水の純度$p_i$ ($1 \leq p_i \leq 100,000,000$)が整数で与えられる。

出力

どろだんごの美しさが何種類あるかを１行に出力する。

入出力例

入力例１

1 2
7
3 5

出力例１

8

入力例２

3 3
1 2 3
1 1 1

出力例２

19