问题1813--智慧出游——计划定制1813: 智慧出游——计划定制
[命题人 : ]
时间限制 : 1.000 sec 内存限制 : 128 MB
题目描述
FC是个很纠结的人，每当要做选择时，他总是不能很快的做出决定，他相信，有很多人也有选择恐惧症，为了帮助这些人解决实际的困难，他想在“智慧出行”APP里推出智能计划定制功能。每一个景点，APP都有游玩最佳时长标注，用户可以选择一些自己想玩的备选景点，每个景点可以输入一个“向往值”，然后用户输入自己总共可游玩的时间，点一下“计划定制”，APP会给用户推荐一组景点组合方案，这个方案是各景点最佳游玩时长的总和不超过用户可游玩时间的所有方案中，“向往值”总和最大的。如果有多个方案符合要求，APP将推荐景点最少的方案，因为这样，游客花费在路上的时间较少，能有更好的旅游体验。如果满足上述要求的方案还有多种，这输出字典序较小的方案。
输入
输入包含n+1行，第一行包含两个整数n（3<=n<=15)，h（5<=h<=20)，n表示接下来有n行数据，h表示用户输入的可游玩时间。接下来的n行，每行包含两个整数，ai，bi（1<=ai<=5，1<=bi<=100），表示第i个景点的最佳游玩时间和“向往值”。
输出
输出包含2行，第一行一个整数，表示推荐方案“向往值”的总和，第二行包含一个整数数列，表示推荐的方案，推荐景点序号从小到大排列。