小红不想做完全背包（hard）

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

题目描述

本题和easy版本的唯一区别是： $p$ 没有必须等于3的限制。

完全背包是一个经典问题，但小红完全不会完全背包，因此她不想做完全背包。

现在小红拿到了一个长的很像完全背包的题，她希望你帮她解决一下。

给定一个背包，有 $n$ 种物品，每种物品的价值为 $a_i$ ，有无穷多个。小红有一个无穷大的背包，她希望往里面放若干个物品，使得最终所有物品的价值之和为 $p$ 的倍数。小红想知道最终至少要放多少物品？

（注意：不能不放物品）

第一行输入两个正整数，用空格隔开。
第二行输入个正整数。

一个整数，代表小红最终要放的物品数量的最小值。

示例1

复制

4 3
1 2 3 4

复制

小红只需要选择一个第三种物品即可。