题目描述

寻宝人找到了 $N$ 件宝藏，第 $i$ 件宝藏的重量为 $w_i$。

他可以选择其中若干件放入背包。如果这些重量相加时，任意一个十进制数位产生进位，背包中的所有宝藏就会消失。例如，$28+41=69$，相加时没有产生进位；$28+45=73$，个位上的 $8+5$ 产生了进位。

请计算在重量相加不产生任何进位的条件下，最多可以选择多少件宝藏。

输入格式

第一行包含一个整数 $N$，表示宝藏数量。

接下来 $N$ 行，每行包含一个整数 $w_i$，表示一件宝藏的重量。

输出格式

输出一个整数，表示最多可以选择的宝藏数量。

5
99
613
8210
124
139

3

数据范围与提示

• $1 \le N \le 20$
• $1 \le w_i \le 10^8$