Large Hadron Collider. He has recently managed to isolate some samples of antimatter in the LHC and would like to
play experiment with them. (Warning: do not try this at home.)
Everyone knows that when matter and antimatter collide, they disappear and release massive amounts of energy in a reaction known as annihilation. If the particles and antiparticles are present in equal amounts, all of them will disappear in the reaction. ~0~ particles with ~0~ antiparticles does not count.calls this a total annihilation. Note that reacting
~N~ samples of matter and ~M~ samples of antimatter, the ~i~-th sample of matter has ~A_i~ particles ~(1 \le i \le N)~, and the ~j~-th sample of antimatter has ~B_j~ antiparticles ~(1 \le j \le M)~. Handling particles is a serious matter, so will not separate any of the particles from a sample. More formally, this means that he can only react a non-empty subset of matter samples with a non-empty subset of antimatter samples.has
fun science, would like you to find out the number of different total annihilation reactions that he can produce with these samples. A reaction is different from another if at least one of the samples used in it is not used in the other.
For all test cases, ~N, M \ge 1~.
Subtask 1 [20%]
~N,M \le 10~
~1 \le A_i, B_j \le 100~
Subtask 2 [80%]
~N + M \le 36~
~1 \le A_i, B_j \le 10^9~
The first line of input will contain ~N~ and ~M~, separated by a space.
The second line will contain ~N~ space-separated integers, ~A_1 \dots A_N~, indicating the number of particles in each matter sample.
The third line will contain ~M~ space-separated integers, ~B_1 \dots B_M~, indicating the number of antiparticles in each antimatter sample.
One integer, the number of different total annihilation reactions thatcan produce.
2 3 1 3 4 4 3
Explanation for Sample Output
~4~ particles of matter in total from the two samples, which he can use to react with either the first or second sample of antimatter. He can also create a reaction involving the second sample of matter and the third sample of antimatter.has