Lamps of the Mind#2581
Arnold, the great mathematician, spent hours staring at his fascinating Abat-Jour. The lamps formed a regular polygon. Some of them, those with red light, interested him the most, others with blue light less so, and some did not interest him at all. Arnold's thoughts were only occupied with the lamps—he formed triangles from them, memorized and compared these triangles, and after a while, forgot all else.
You have been invited to help conduct a study that may help unveil Arnold's genius. It is known that Arnold preferred some colors over others, so restrictions were introduced on the number of lamps of each color that can be present in the considered triangles. Arnold remembered only the geometric forms (triangles with the same set of side lengths are considered identical), not the position or color of the lamps. As your first task, calculate the number of distinct triangles in the mind of the great mathematician.
The first line contains two integers and (3 \leq N \leq 3000, 1 \leq K \leq N), the number of lamps that form the regular polygon and the number of colors, respectively.
The second line contains integers c_i (1 \leq c_i \leq K), denoting the colors of the lamps.
The third line contains integers l_i (0 \leq l_i \leq 3). This means that triangles containing more than l_i lamps of color are not considered by the mathematician.
Output a single integer—the number of distinct triangles that can fit in the mind of the great mathematician.
Exemple 1