Coding is the closest thing we have to superpower !

3850 : 状压dp-任务安排
描述

有n个任务,每个任务有一个截止时间,超过截止时间一天,要多扣一分。
求如何安排任务,使得扣的分数最少。

输入

第一行一个整数n(1 \le n \le 15)
接下来n行,每行一个非空字符串(长度不超过10,只由英文字母组成)表示任务的名称和两个整数(不超过1000的正整数),分别表示任务的截止时间和完成任务需要的天数。 这n个任务是按照字符串的字典序从小到大给出。

输出

输出最少扣的分数,并输出一个完成任务的方案,如果有多个方案,输出字典序最小的一个。

样例

输入

3
Computer 3 3
English 20 1
Math 3 2

输出

2
Computer
Math
English

输入

3
Computer 3 3
English 6 3
Math 6 3

输出

3
Computer
English
Math
标签
语言:
主题: