Laundry

A few friends decided to do their laundry together. They are all very tidy, so on each day every friend wears one clean pair of socks and one clean shirt. All of their dirty socks and shirts have now been washed, and they want to hang everything up to dry with clothespins.

They agreed on the following rules:

• every sock is fastened to the line with a single clothespin;
• every shirt is fastened with three clothespins;
• all clothespins used on one person's socks must have the same color;
• all clothespins used on one person's shirts must have the same color;
• clothes belonging to different people must not use clothespins of the same color;
• subject to all of the above, they want to use as few distinct clothespin colors as possible.

If friend $i$ collected laundry for $d_i$ days, that friend has $d_i$ pairs of socks and $d_i$ shirts, and therefore needs $2 \cdot d_i$ clothespins for the socks (all of one color) and $3 \cdot d_i$ clothespins for the shirts (all of one color). A person may use the same color for both their socks and their shirts, or two different colors.

The friends have gathered all their clothespins and counted how many they have of each color. Help them find the smallest number of distinct colors they need to use.

The first line contains two integers $n$ and $k$ ($2 \le n, k \le 1{,}000{,}000$) — the number of friends and the number of available clothespin colors.

The second line contains $n$ integers $d_1, d_2, \ldots, d_n$ ($1 \le d_i \le 1{,}000{,}000$), where $d_i$ is the number of days friend $i$ was collecting laundry.

The third line contains $k$ integers $l_1, l_2, \ldots, l_k$ ($1 \le l_i \le 4{,}000{,}000$), where $l_i$ is the number of clothespins of the $i$-th color.

Print a single integer: the minimum number of distinct clothespin colors needed to hang up all the laundry according to the rules. If it is impossible, print the single word NIE instead.

In the first example there are two friends. The first friend ($d_1 = 3$) needs $6$ clothespins for socks and $9$ for shirts; the second friend ($d_2 = 4$) needs $8$ for socks and $12$ for shirts. Since $8 + 12 = 20$, the second friend can use the first color (which has $20$ clothespins) for both socks and shirts. The first friend can then use, for example, the second and the fourth colors (each with $10$ clothespins) — one for the socks and one for the shirts. Three colors are used in total.