Imagine a little while from now RedMart is closing in fast on delivering its 1 millionth order. The marketing team decides to give the customer who makes that order a prize as a gesture of appreciation. The prize is a fun one: the lucky customer gets a RedMart delivery tote and 1 hour in the warehouse. Use the hour to fill up the tote with any products you desire and take them home for free.

The only restrictions are:

You can only take 1 of any product.

Everything you take, together, must completely fit into a tote.

The tote's usable space is 45 centimeters long, 30 wide and 35 high. (You can assume that if the products fit into the tote both individually and together by total volume, that you'll be able to find a way to pack them in.)

Here is what a tote looks like:


In a stunning turn of events you are the person who places the 1 millionth RedMart order and are the winning customer. Congratulations, what luck! Your run of luck continues when you come into possession of a file describing RedMart's products. For each product it lists the price, length, width, height and weight. Being a software engineer you are quite analytical and clever. So naturally you decide to optimize this opportunity by figuring out ahead of time what products you will take, and then spend your hour leisurely collecting them around the warehouse.

In addition to the rules of the contest your personal preferences are:

Maximize the dollar value of the products in the tote.

A lighter tote is better, as long as you don't sacrifice any dollar value.

Your challenge is to write a program in your favorite programming language to enact your plan. Use this file as input. It contains 20,000 products, one per line. Each line has the following fields separated by a comma:

product ID, price, length, width, height, weight

Price is in cents, dimensions are in centimeters, weight is in grams.

Send your code or a github link (and a resume if you like) to [?????? at redmart dot com], replacing "??????" with the sum of product IDs of all the products you will take. So if you take just two products, with IDs 111111 and 222222, the email address would be [333333 at redmart dot com]. If your e-mail gets through - you got the right answer.

Good luck and have fun!