青蛙
题号:NC236191
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

有 m 颗石头排成一个环,编号为 0 到 m-1 。有 n 只青蛙在 0 号石头上,第 i 只青蛙每次能恰好跳过 a_i 颗石头。具体地,如果第i只青蛙当前在编号 x 的石头上,它下一跳会到达  的石头(因为石头是成环排列的)。

青蛙 i 每跳到一颗石头上,这颗石头都会被青蛙 i 占领,即使这只青蛙跳出了这颗石头,石头还是被青蛙 i 占领,当另一只青蛙 j 跳到该石头上后,这块石头同时被 i j 占领。青蛙们现在想知道,当它们跳跃次数足够多之后,最终有多少颗石头被两只及以上的青蛙占领。因为这样的石头个数可能很多,你只需要输出这些石头的编号之和。

输入描述:

第一行输入两个整数  ,分别表示青蛙数和石头数。

第二行输入 n 个整数  ,表示每只青蛙每次跳过的石头数。

输出描述:

输出一行一个整数,表示至少会被两只青蛙占领的石头编号之和。

示例1

输入

复制
2 12
9 10

输出

复制
42
示例2

输入

复制
9 96
81 40 48 32 64 16 96 42 72

输出

复制
1872