DMOPC '15 Contest 3 P5 - Total Annihilation

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types

quantum works part-time at CERN as a particle physicist, where he spends his days smashing particles together in the famous 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. quantum calls this a total annihilation. Note that reacting 0 particles with 0 antiparticles does not count.

quantum has 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 quantum 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.

For fun science, quantum 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

Input Specification

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.

Output Specification

One integer, the number of different total annihilation reactions that quantum can produce.

Sample Input

2 3
1 3
4 4 3

Sample Output


Explanation for Sample Output

quantum has 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.


There are no comments at the moment.