Your friend has recently been looking through a catalog, and has selected several items she wishes to buy. Because of a sales promotion, she has earned credit towards free or discounted products. Each item has a cost, and a point value. For her referrals, your friend has earned a certain number of points which may be redeemed for items, and a certain number of "half price" items. Additionally, she receives a fixed percentage discount on all other items (this is not cumulative with half-price items). All prices are rounded up after applying discounts.
Your friend's order is subject to the following restrictions:
- Each item must be purchased with points, purchased at half price, or purchased at the fixed discount rate.
- Purchasing an item with points is all or nothing; you cannot, for instance, pay for an item partially with points and pay the remainder in cash.
- All points must be used.
- All half-price items must be used.
- All items on the wishlist must be purchased.
Your friend is very excited to place her order, but is very frustrated with what she has found to be a confusing incentive system. Being frugal-minded, she wants to get everything on her wishlist at the least possible out-of-pocket expense. Knowing your enjoyment of these type of problems, she has come to you for assistance.
You are given an int, points, indicating the number of points your friend must spend; an int, halfPrice, indicating the number of items which are to be purchased at half price; and an int, discount, indicating the fixed discount percentage on all remaining items. Finally, you are given a String, items, indicating the list of items on your friend's wishlist. Each element of items will be in the form "pointValue price" (quotes added for clarity), where pointValue and price are both positive integers with no leading zeros. pointValue and will be between 1 and 9999, inclusive. price will be between 1 and 99999, inclusive. You are to return an int indicating the minimum out of pocket expense your friend must pay to get the items on her wishlist.