You have found a cave filled with treasures, and you want to take as much as you can. However, you can only make one trip, so you decide to use the following strategy. You will take the treasures with the maximal total cost, but with a total weight no greater than **W**. Each treasure is characterized by its weight, cost, and whether it can be divided. For example, a bar of gold can be divided into two smaller bars of any size (with costs proportional to the cost of the original bar), but a cut-glass bowl cannot be divided because it would become worthless.
You will be given a String[] **treasures** and an int **W**. Each element of **treasures** will be formatted as "weight cost can_be_divided" (quotes for clarity), where weight and cost are integers and can_be_divided is either 'Y' or 'N'. Return the total cost of the treasures you will take. |