题目描述

给出一个序列 $a_1,a_2,\ldots,a_n$，要求从中找出一个子序列，使子序列中任意相邻两个数满足：前一个数的末位数字是后一个数的首位数字的约数。

例如，$302,817,739000$ 是一个满足要求的序列，因为 $302$ 的末位数字 $2$ 是 $817$ 的首位数字 $8$ 的约数；$817$ 的末位数字 $7$ 是 $739000$ 的首位数字 $7$ 的约数。但是 $70,1$ 不满足要求，因为 $0$ 不是 $1$ 的约数。

在所有满足要求的子序列中，元素总和的最大值是多少？单独一个数也算满足要求的子序列。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出满足要求的子序列的最大元素和。

输入输出样例

输入 #1

5
14 23 900 46 60

输出 #1

923

说明/提示

样例中选择子序列 $\{23,900\}$ 可以得到最大和。子序列 $\{14,46,60\}$ 也满足要求，但元素总和较小。

答案可能超过 32 位整数类型的范围。

数据范围

$1\le n\le 10^5$，$1\le a_i\le 10^9$。

5
14 23 900 46 60

923

26
202067770 474103211 134726664 719430913 17949156 634065906 751402096 321295737 580718665 157071855 581692952 205217471 196210295 931853864 493757891 759291864 38436664 707050583 861416721 464960238 941482329 112783568 642342418 916639961 194521603 353031778

7293728310

31
637228298 543227863 452737024 791901341 952314590 860331938 80666033 274978719 319358182 943631683 58335985 390465138 381062968 579491906 77268591 831552460 428999849 276071908 780537883 160548536 430875036 895450957 882686488 193811164 330086227 508084612 982393671 122920551 781539673 246146131 100482711

4743986763