Test your might

Packing your Dropbox

When you're working with petabytes of data, you have to store files wherever they can fit. All of us here at Dropbox are always searching for more ways to efficiently pack data into smaller and more manageable chunks. The fun begins when you bend the rules a little bit and visualize it in two dimensions.

You'll be given a list of rectangular "files" that you'll need to pack into as small a "Dropbox" as possible. The dimensions of each file will be specified by a tuple (width, height), both of which will be integers. The output of your function should be the area of the smallest rectangular Dropbox that can enclose all of them without any overlap. Files can be rotated 90° if it helps. Bonus points if you can draw pictures of the winning configurations along the way. While drawing pictures, any files sharing dimensions should be considered identical/interchangeable.

Input

Your program must read a small integer N (1 <= N <= 100) from STDIN representing the maximum number of files to consider, followed by the width and height of each file, one per line.

Output

Output should be simply be the area of the smallest containing Dropbox. If you want to print pretty pictures, send that to stderr. Only the output on stdout will be judged.

3
8 8
4 3
3 4

88

11x8:
+ - - - - - - + + - + 
|             | |   | 
|             | |   | 
|             | + - + 
|             | + - + 
|             | |   | 
|             | |   | 
+ - - - - - - + + - + 

8x11:
+ - - - - - - + 
|             |
|             | 
|             | 
|             | 
|             | 
|             | 
+ - - - - - - + 
+ - - + + - - + 
|     | |     | 
+ - - + + - - + 

11x8:
+ - + + - - - - - - + 
|   | |             | 
|   | |             | 
+ - + |             | 
+ - + |             | 
|   | |             | 
|   | |             | 
+ - + + - - - - - - + 

8x11:
+ - - + + - - + 
|     | |     | 
+ - - + + - - + 
+ - - - - - - + 
|             | 
|             | 
|             | 
|             | 
|             | 
|             | 
+ - - - - - - + 

File Events

To keep all your computers in sync, Dropbox watches your file system for any changes within your Dropbox folder. Unfortunately, in many cases the file events received are too coarse to be presentable to non-savvy users, usually just an ADD event for any new file and a DEL event for any file that went missing.

You'll be given a list of ADD/DEL file events that should be processed and turned into a human-readable event feed that includes richer events like file and directory renames, moves, and copies.

Input

Your program must read an integer N (1 <= N <= 50000) from STDIN representing the number of file events in the test input, followed by that many file event rows. Each row will have the file event type, a UNIX timestamp of when the event occurred, the path of the file relative to the Dropbox root, and an 8-character hash of the contents (or former contents) of the file. Each row is separated by a space. No file paths include spaces. Directories are files too and may be empty (they'll have "-" as their file hash).

Output

Your output should be a series of English sentences to stdout, one per line, in some way describing the file events in a user-friendly manner. There is no objectively 'right' answer here, and in fact there may be multiple ways to interpret a provided list of file events. We'll be judging submissions on a number of criteria including raw efficiency, friendliness of output, ability to handle ambiguity, and more. As one example, the sample output below is (probably) the correct interpretation of the input file events, but is not particularly user-friendly. Feel free to deviate substantially from the sample.

6
ADD 1282352346 /test -
ADD 1282353016 /test/1.txt f2fa762f
DEL 1282354012 /test -
DEL 1282354012 /test/1.txt f2fa762f
ADD 1282354013 /test2 -
ADD 1282354013 /test2/1.txt f2fa762f

Added dir /test.
Added file /test/1.txt.
Renamed dir /test -> /test2.

The Dropbox Diet

Of the boatload of perks Dropbox offers, the ones most threatening to our engineers' waistlines are the daily lunches, the fully-stocked drink fridge, and a full-length bar covered with every snack you could want. All of those calories add up. Luckily, the office is also well-equipped with ping-pong, a DDR machine, and a subsidized gym right across the street that can burn those calories right back off. Although we often don't, Dropboxers should choose the food they eat to counterbalance the activities they perform so that they don't end up with caloric deficit or excess.

Help us keep our caloric intake in check. You'll be given a list of activities and their caloric impact. Write a program that outputs the names of activities a Dropboxer should choose to partake in so that the sum of their caloric impact is zero. Once an activity is selected, it cannot be chosen again.

Input

Your program reads an integer N (1 <= N <= 50) from STDIN representing the number of list items in the test input. The list is comprised of activities or food items and its respective calorie impact separated by a space, one pair per line. Activity names will use only lowercase ASCII letters and the dash (-) character.

Output

Output should be sent to stdout, one activity name per line, alphabetized. If there is no possible solution, the output should be no solution. If there are multiple solutions, your program can output any one of them. Solutions should be non-trivial, so don't send us cat > /dev/null, you smart aleck.

2
red-bull 140
coke 110

no solution

12
free-lunch 802
mixed-nuts 421
orange-juice 143
heavy-ddr-session -302
cheese-snacks 137
cookies 316
mexican-coke 150
dropballers-basketball -611
coding-six-hours -466
riding-scooter -42
rock-band -195
playing-drums -295

coding-six-hours
cookies
mexican-coke