005 - カードゲーム

たくさんの青いカードと赤いカードがテーブルの上にある．各カードの表面には1より大きい整数がひとつ印刷されている．同じ整数値がいくつかのカードに印刷されていることがある．

青いカードの数値と赤いカードの数値が1より大きい同じ整数値で割りきれるとき，その青いカードと赤いカードはペアにすることができる． 1枚の青いカードとペアにできる複数の赤いカードがありうる．また，1枚の赤いカードとペアにできる複数の青いカードがありうる．青いカードと赤いカードを1枚ずつ選んでペアにしたら，その2枚のカードをテーブル上の全体のカードから取り除く．

図 E-1: 青いカード4枚と赤いカード3枚

たとえば，図E-1には，青のカードが4枚，赤のカードが3枚ある． 4枚の青のカードに 2, 6, 6, 15 が印刷され， 3枚の赤のカードに 2, 3, 35 が印刷されている．ここで，青と赤のカードのペアを以下のようにして作ることができる．最初に，「青の2」と「赤の2」をペアにして取り除くことができる．次に，「青の6」のうちのひとつと「赤の3」をペアにして取り除くことができる．そして，「青の15」と「赤の35」をペアにして取り除くことができる．この場合，取り除いたペアは3組である．

ペアの個数はペアを作るカードの選び方によって変化することに注意せよ．最初に「青の15」と「赤の3」というペアを作ってこれを取り除くこともできる．この場合，もうひと組しかペアを作れず，合わせて2組のペアしか取り除けない．

あなたの仕事は，テーブル上のカードから最大何組のペアが取り除けるかを求めることである．

入力は複数のデータセットからなる．データセットの総数は100以下である．各データセットは，次の形式をしている．

m n
b₁ ... b_k ... b_m
r₁ ... r_k ... r_n

m と n はそれぞれ青いカードと赤いカードの枚数を示す． 1 ? m ? 500 および 1? n ? 500 と仮定してよい． b_k (1 ? k ? m) およびr_k (1 ? k ? n) は，それぞれ青と赤のカードに印刷された数であり，それらは2以上10000000 (=10⁷)未満の整数である．入力データの整数は1個のスペースまたは改行で区切られている． b_m と r_n の各々の直後は改行である．データセットには他に余計な文字は無い．

入力の終わりはスペースで区切られた2個のゼロからなる行である．

各データセットに対し，ペアの組数の最大値を表す整数を1行に出力せよ．

4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961
0 0

3
1
0
4
9
18
85