3726. 烟雾与火焰

【题目背景】

$2012$ 年, 永远 $16$ 岁的世界守护者, 天鸟 那由多, 发现这个世界危在旦夕。五年前 $17$ 岁的天才生物学家, 鹰白 榧夜, 在拒绝为某人提供克隆人技术后遭到暗杀, 现在, 由于克隆自己重回世间的需要, 榧夜使整个东京陷入一片混乱与恐惧之中。为了维护世界和平, 拯救天下苍生, 那由多需要毁掉榧夜曾经的实验室。然而整个东京都实在是太大了, 那由多找不出实验室, 请你帮助她拯救世界。

【题目描述】

为了毁掉实验室, 天才少女那由多决定把整个东京(包括她自己)全部炸上天, 以此使这个世界变得稳的一批。那由多为你提供的数据最多包括有 $n$ 座建筑, 而她拥有三种炸药, 若在第 $i$ 栋建筑安放第 $k$ 种炸药, 则会引爆该建筑和第 $i+p_k$ 座建筑。由于被榧夜的爪牙所阻挠, 那由多只能通过引爆第一座建筑中的炸药并引发连锁反应以炸毁东京都。现在请你帮助她计算她最多可以炸毁多少座建筑。

【输入格式】

四个数: $n$, $p_1$, $p_2$, $p_3$;

【输出格式】

一个正整数 $ans$。

【样例输入】

15 4 7 9

【样例输出】

 9

【样例说明】

可以炸毁的建筑有：$1$, $5$, $8$, $9$, $10$, $12$, $13$, $14$, $15$。

【数据规模与约定】

对于 $30$% 的数据, $1 \le n \le 10$;

对于 $60$% 的数据, $1 \le n \le 1000000$;

$1 \le p_1,p_2,p_3 \le n \le 2^{63} - 1$, $1 \le p_1,p_2,p_3 \le 10^5$。

大样例:戳我

【来源】

蒟蒻出题人: $seium$