eolymp
bolt
Try our new interface for solving problems
Məsələlər

Лампы в памяти

Лампы в памяти

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Великий математик Арнольд часами смотрел на свой захватывающий Абат-Джур. Лампы в нем образуют правильный многоугольник. Лампы с красным светом интересовали его больше всего, лампы синего света меньше, а некоторые лампы не интересовали Арнольда и вовсе. Мысли Арнольда были заняты лишь лампами - он конструировал из них треугольники, запоминал и сравнивал их, а через некоторое время выбрасывал из головы.

Вас наняли для проведения исследования, которое поможет приоткрыть завесу над гением Арнольда. Известно, что Арнольд предпочитает некоторые цвета. Поэтому были введены ограничения на количество ламп каждого цвета, которые могут использоваться в треугольниках. При этом только геометрические формы (треугольники с одним и тем же множеством длин сторон считаются одинаковыми), но не положение или цвет лампы, запомнил Арнольд. В качестве первой задачи Вам необходимо вычислить количество треугольников в уме великого математика.

Giriş verilənləri

Первая строка содержит два целых числа N и K (3N3000, 1KN), разделенных пробелом - количество ламп, образующих правильный многоугольник, и количество их цветов соответственно. Вторая строка содержит N целых чисел c_i (1c_iK), разделенных пробелом - цвета ламп. Третья строка содержит K целых чисел l_i (0l_i3). Они означают, что треугольники, содержащие более l_i ламп i-го цвета, не рассматриваются великим математиком.

Çıxış verilənləri

Вывести одно целое число - количество разных треугольников, которое может поместиться в уме великого математика.

Nümunə

Giriş verilənləri #1
5 3
1 2 2 1 3
2 1 0
Çıxış verilənləri #1
1