← 返回题目列表

Codeforces · 271/E

E. 三匹马

中文机器翻译题面 查看原题

马地里住着三匹马:一匹灰色,一匹白色,一匹灰白色。马是非常有趣的动物,这就是为什么它们喜欢特殊的卡片。每张卡片都必须包含两个整数,第一个整数位于卡片的顶部,第二个整数位于卡片的底部。我们将上面有 a、下面有 b 的卡片表示为 (a, b)。

三匹马中的每一匹都可以绘制特殊卡。如果你向灰马出示一张 (a, b) 卡,那么这匹马就可以画一张新的 (a + 1, b + 1) 卡。如果你向白马展示一张 (a, b) 卡片,其中 a 和 b 是偶数整数,那么这匹马就可以画出一张新的 $$( \frac { a } { 2 }, \frac { b } { 2 } )$$ 卡片。如果你向灰白马出示两张牌(a,b)和(b,c),那么他可以画一张新的(a,c)牌。

Polycarpus 确实想要获得 n 张特殊牌 (1, a1), (1, a2), ..., (1, an)。为此,他要去马场。他可以将一张 (x, y) 卡带到马地,使得 1 ≤ x < y ≤ m。有多少种选择卡牌的方式,以便他可以在马地里执行一些动作,并获得所需的卡牌?

波利卡普斯只能通过上述行动才能从马身上获得牌。除了他需要的牌之外,波利卡普斯还可以得到额外的牌。

输入

第一行包含两个整数 n, m (1 ≤ n ≤ 105, 2 ≤ m ≤ 109)。第二行包含整数序列 a1, a2, ..., an (2 ≤ ai ≤ 109)。请注意,序列中的数字可以重合。

行中的数字由单个空格分隔。

输出

打印一个整数——问题的答案。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

1 6
2

输出 #1

11

输入 #2

1 6
7

输出 #2

14

输入 #3

2 10
13 7

输出 #3

36