410056: GYM103934 D Inflation

In the decade of the 2010s, Egypt went through a very high inflation period. This made the price of all local goods to radically increase, so radically that it stopped being feasible for the prices to be written as 64 bit integers, as it was done before. The sellers, not wanting to stop selling their items, had to use their creativity to find a way to write their products prices.

Let $$$a$$$ be an array of $$$n$$$ distinct primes $$$a_1 \dots a_n$$$. We define $$$P$$$ as the product of these primes. Thus:

$$$$$$P = \prod_{i=1}^{n} a_i.$$$$$$

The array $$$b$$$ of prices of the $$$n$$$ items in the store is defined as $$$b_i = P/a_i$$$, in which $$$b_i$$$ is the price of the $$$i$$$-th item in Egyptian Pounds.

Sara is a competitive programmer, and so she gets many prized in American Dollars. With a nice exchange rate, she now holds great wealth. She has some amount $$$d$$$ of Egyptian Pounds, that can be written as the product of $$$m$$$ not necessarily distinct primes $$$c_i$$$. Thus:

$$$$$$\displaystyle d = \prod_{i=1}^{m} c_i.$$$$$$

Since Sara plans to study abroad, she would like to spend all of her pounds. She asked for your self to determine wether it is possible to buy some of the $$$n$$$ itens in such a way as to spend all the money she has: $$$d$$$ pounds. Since the crisis affected the shops, only one of each product is available.

The first line of the input consists of 2 integers $$$n$$$ and $$$m$$$, the number of items and the amount of prime factors in the number $$$d$$$ respectively $$$(1 \leq n , m \leq 3 \cdot 10^3)$$$. The following line consists of $$$n$$$ distinct primes $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$, that define the prices of the $$$n$$$ items. The next line has $$$m$$$ not necessarly distinct primes $$$c_i$$$, the prime factors of the value $$$d$$$ $$$(1 \leq c_i \leq 2 \cdot 10^{18})$$$.

Print 'S' if it is possible for Sara to buy some of the $$$n$$$ items so that their sum equals $$$d$$$. Print 'N' otherwise.

3 2
2 3 5
3 7

S

3 3
2 3 5
2 2 11

N

2 4
5 11
2 2 2 2

S

In the first test case, $$$P = 30$$$, hence the array $$$b$$$ of prices is $$$b = (15,10,6)$$$. The value $$$d$$$ that Sara has is 21, which might be spent if she buys the first and last items. Therefore the answer to this case is yes ('S').