TopCoder

暴力又被TLE
PY派對

User's AC Ratio

55.6% (5/9)

Submission's AC Ratio

15.6% (5/32)

Tags

Description

你喝過程三鼎的加工奶茶嗎?程三鼎是一家專門製作人造黑糖青蛙奶茶的知名店舖的創始人,他製作的人造青蛙撞奶不論是外表或者是味道都維妙維肖、栩栩如生,更重要的是價格公道坦蕩蕩,因此遠近馳名,每天都一開幕就人人爭先恐後地搶買,顧客排隊時不小心跌倒導致被後面的群眾踐踏而亡的新聞時有所聞。

程三鼎退休後用存下的大筆金錢蓋了一座美麗的花園,裡面滿滿地栽植了各式各樣他喜歡的花草,命名為「阿鼎の大好花園」,簡稱為「鼎園」。為了追求美的極限,程三鼎甚至成立了一間實驗室專門進行植物研究以及品種改良等等,因此花園內部到處都是獨一無二豔冠群芳的超級改良種,無論是氣質、花色、香味、姿態等皆是上乘之選。而這花園中當然沒有遺漏掉月亮山上獨傲的特有種──高山棕櫚!相傳鼎園中的高棕櫚口感$Q$彈、多汁香甜,吃過的円円都說讚,也因此引此了円円族長老的注意,決定在某個假日團體包車去參觀。

到了現場後,円円們發現鼎園內的高棕櫚實在是太好吃了,一吃難罷口,因此決定向程三鼎打包一些精挑細選的高棕櫚回去吃。不過鼎園離月亮山有一段距離,如果沒有妥善保鮮,在路途上就有一些高棕櫚會過熟而壞掉,對円円來說簡直是要了他的命,因此他們自備了一些保鮮盒來裝高棕櫚。裝高棕櫚的規則是這樣的:

1. 不同的高棕櫚可能會因為生長時間不同,有的生(可以帶回家好好調教,熟了之後會更好吃)有的熟(可以馬上吃),我們用「成熟度」來表達一個高棕櫚的成熟程度。

2. 每一個保鮮盒都有一個「保鮮值」,代表盒內高棕櫚「成熟度總和」的最大上限。如果盒內的高棕櫚成熟度總和還沒超過保鮮值,那放幾個都可以;如果超過了那絕對不行,因為這樣子保鮮盒會齁不住導致整盒的高棕櫚都壞掉。

3. 因為円円族很喜歡數學,所以他們挑選要帶回家的高棕櫚之間必定存在「倍數關係」。也就是說,對於任意兩個円円要帶回家的高棕櫚 A 和 B,要嘛 A 的成熟度是 B 的成熟度的倍數,要嘛 B 的成熟度是 A 的成熟度的倍數。

現在円円們已經選好想要帶走哪些高棕櫚回家了(由於上述的第三點,這些高棕櫚之間都存在倍數關係),但是由於保鮮盒容量有限,並不一定所有的高棕櫚都可以成功帶回家。於是円円們委託你寫一個程式幫忙計算,到底他們本次最多可以從鼎園帶走多少個高棕櫚呢?

Input Format

輸入的第一行包含一個正整數 $T (T \leq 30)$,代表接下來有幾組測試資料。每組測試資料的第一行包含兩個正整數 $n(1\leq n \leq 10^ 5)$ 和 $m(1\leq m \leq 10^ 5)$,以一個空白隔開,分別代表保鮮盒的數量以及円円想帶回家吃的高棕櫚的數量。

接著第二行有 $n$ 個正整數 $M_i(1 \leq M_i \leq 10^ 6, 1 \leq i \leq n)$,以一個空白隔開,代表 $n$ 個保鮮盒的保鮮值;最後第三行是 $m$ 個正整數 $F_j(1 \leq F_j \leq 10^ 6, 1 \leq j \leq m)$,以一個空白隔開,代表 $m$ 個要帶回家吃的高棕櫚的成熟度。

對於$40\%$的測試資料保證$1\leq n,m\leq 20$
對於$70\%$的測試資料保證$1\leq n,m\leq 1000$
對於$100\%$的測試資料保證$1\leq n,m\leq 10^ 5$

Output Format

對於每筆測試資料輸出円円在想帶回家的高棕櫚中,最多可以選幾個帶回家享用。

Sample Input 1

1
2 4
13 9
4 12 2 4

Sample Output 1

3

Hints

円円最多可以把 $3$ 個高棕櫚帶回家。

Problem Source

NEOJ Problem 90

Subtasks

No. Testdata Range Constraints Score
1 0 40
2 0~1 30
3 0~2 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 65536 1 2 3
1 3000 65536 65536 2 3
2 3000 65536 65536 3