6722번 - Christmas presents 다국어

The local Santa Claus needs help! He has realized that he cannot afford to give every child a present any longer, so he needs your help to select those lucky children that will get a present. He has made a record for each child containing the child’s level of excitement and frustration when getting or not getting a present, and now he wants a program that ensures that maximum total satisfaction is reached while preventing the total expenses to exceed his upper limit. The total satisfaction is defined as the sum of all excitements for those children that get presents, minus the sum of frustrations for the others.

First line: n — the number of children (integer less or equal 1000), and p (integer less or equal 1000) — the expense limit.

Next n lines: 3 integers: price, excitement level and frustration level for each child. You can assume that all the prices, and excitement and frustration levels are nonnegative integers.

First line: Total satisfaction. Second line: A string of n zeroes and ones — 0 means that this child does not get a present, 1 means that s/he gets a present.