Задача №114794. Прыгающий аппарат
Изобретатель решил испытать свой новый аппарат для длинных прыжков. Для этого он пришёл на испытательный полигон. Полигон представляет собой бесконечное клетчатое поле.
Изначально прибор находится в клетке \((0, 0)\). У аппарата есть \(n\) пружин, \(i\)-я пружина имеет силу \(l_i\) и позволяет прыгнуть на \(l_i\) клеток вверх или вправо. Таким образом, из клетки \((x, y)\) эта пружина позволяет попасть либо в клетку \((x + l_i, y)\), либо в клетку \((x, y + l_i)\). После прыжка пружина отбрасывается и не может быть использована повторно. Аппарат может использовать пружины в любом порядке.
Во время испытаний клетки, над которыми будет пролетать прибор, окажутся запачканы машинным маслом. Чтобы не чистить после себя поле, изобретатель решил положить на каждую клетку, над которой потенциально может пролететь прибор, защитный коврик.
Теперь изобретателю интересно, какое количество защитных ковриков ему нужно принести с собой на испытание.
В первой строке входных данных находится число \(n\) — количество пружин у аппарата (\(1 \le n \le 100\)). В следующей строке находится \(n\) натуральных чисел \(l_i\) — силы пружин (\(l_i \ge 1\); \(1 \le l_1 + l_2 + \dots + l_n \le {10}^6\)).
Выведите одно число — количество клеток, которые могут быть запачканы при прыжках аппарата.
2 4 2
22