CF295C Greg and Friends

一天，Greg 和他的朋友们在森林里散步。包括 Greg 在内，一共有 $n$ 个人同行。不久，他们遇到了一条河。大家决定要过河。幸运的是，河岸边正好有一只船。已知这条船最多只能承载总重量不超过 $k$ 千克的人。 Greg 立即把大家的体重记了下来。结果发现每个人的体重要么是 $50$ 千克，要么是 $100$ 千克。现在 Greg 想知道，要将所有人都运送到对岸，这条船至少需要渡河多少次。 每次划船至少需要一个人在船上才能操控船，船每次渡河时，只要总重量不超过 $k$，船上可以有任意数量的人。 Greg 还想知道，在最少渡河次数的方案中，有多少种不同的运送方式。如果某次渡河选择的人集合不同，那么视为不同的方式。 请你帮助 Greg 解决这个问题。

第一行包含两个整数 $n$ 和 $k$，表示包括 Greg 在内的人数，以及船的最大承重。$1\leq n\leq 50,\,1\leq k\leq 5000$。 第二行包含 $n$ 个整数，表示每个人的体重。每个人的体重为 $50$ 或 $100$ 千克。 你可以认为 Greg 和他的朋友们已经被编号。

第一行输出一个整数，表示最少需要渡河的次数。如果无法将所有人都运送到对岸，输出 $-1$。 第二行输出采取最少渡河次数的方案数对 $1000000007$ ($10^9+7$) 取余的结果。如果无法将所有人都运送到对岸，输出 $0$。

在第一个样例中，Greg 独自一人，因此只需一次渡河。 在第二个样例中，应按下面的计划操作： 1. 运送两个 $50$ 千克的人。 2. 送回一个 $50$ 千克的人。 3. 运送一名 $100$ 千克的人。 4. 送回一名 $50$ 千克的人。 5. 运送两个 $50$ 千克的人。 一共需要 $5$ 次渡河。在步骤 $2$ 的选择不同的人，会有两种不同的方式。 由 ChatGPT 5 翻译