#P5362. 准确支付

    ID: 5662 传统题 1000ms 256MiB 尝试: 15 已通过: 4 难度: 3 上传者: 标签>动态规划背包问题dp教师测试算法组普及/提高−数组排序

准确支付

题目描述

一个特殊的购物中心,结账时必须准确支付所有金额。LX 手上有 nn 张纸币,账单显示 mm 元。请帮他确定支付方式。若支付方式不唯一,输出字典序最小的。若无法支付,输出 No Solution

输入格式

第一行包含两个整数 nnmm,分别表示纸币数量以及需要支付的金额。

第二行包含 nn 个整数,表示每张纸币的面额。

输出格式

共一行,按照面额升序的顺序,输出用来支付的所有纸币的面额。

如果支付方式不唯一,则输出最小的支付面额序列(即字典序最小)。如果无解,则输出 No Solution

样例

8 9
5 9 8 7 2 3 4 1
1 3 5

样例解释
可以选择面额为 1,3,51, 3, 5 的纸币,总和为 99,且这是字典序最小的支付方案。其他方案如 4,54,5 等字典序较大。

数据范围

  • 1n1041 \leq n \leq 10^4
  • 1m1001 \leq m \leq 100
  • 纸币面额均为正整数,不超过 100100