### James S. Plank

Sat Nov 19 10:11:08 EST 2016

In case topcoder's servers are down, here is a summary of the problem:
• You are given a vector of integers, S and a number P.
• Your goal is to chose P pairs of numbers from S such that the sum of the differences of each pair is minimized.
• S's size is ≤ 1000.
• The elements of S are between 1 and 109.
• P times two is ≤ S.

Examples:

 Example Input Output 0 {42, 37, 84, 36, 41, 42}, 2 1 1 {42, 37, 84, 36, 41, 42}, 3 42 2 {5, 2, 8, 8, 6, 7, 3, 7, 4, 2, 4, 5, 3, 6}, 7 0 3 {17, 3, 13, 3, 2, 17, 11, 5, 5, 7, 11, 7, 13, 19}, 7 4 4 This is a big one -- just read the main. 12866316 5 { 20, 1000, 1050, 1099, 1500, 3000, 3010, 3022, 6000}, 3 401

Your temptation here is to solve this with a greedy algorithm. Something like: choosing the best pair of socks, and removing them from the Sock array, and then maybe putting them back and matching them with the socks around them.

Don't give into that temptation, because this problem has a really straightforward dynamic programming solution. First, sort the socks. Now, let's consider the first sock. Either you are going to match that sock with the next one, or you are not going to match it at all. Let's consider both cases:

• If you do match it with the next one, then you can remove the socks, and solve the problem where you have to match P-1 pairs of socks.
• If you do not match it, then you can remove it, and solve the problem by finding P pairs of socks from the remaining socks.

So, what I did was sort the socks and make the sock vector a member of my class. Then, I wrote the following method:

 ```int GD(int index, int npairs) ```

This method returns the best answer when I need npairs pairs of socks, and I'm ignoring any socks whose indices are less than index. I'll solve getDifference() by returning GD(0,P).

I have two base cases. If npairs is zero, then my answer is zero, because I have not more matches to make. If index is too big, and I don't have enough socks to make even one pair of socks, then I return a large sentinel -- 1,000,000,001.

Otherwise, I have two cases to try:

1. Matching S[index] with S[index+1], and calling GD(index+2, pairs-1).
2. Ignoring S[index] and simply calling GD(index+1).
The better of these two is my answer.

Below, I'm going to show you the memoization cache for each of the example problems. I've added and example #5 to the mix too: { 20, 1000, 1050, 1099, 1500, 3000, 3010, 3022, 6000}. This is a nice example to step through by hand if you're having problems. Use the printouts below to help you.

### Example 5 - Answer is 401

Socks: 20 1000 1050 1099 1500 3000 3010 3022 6000

 Index / Pairs 1 2 3 0 -1 -1 401 1 -1 -1 401 2 -1 49 1500 3 -1 401 2978 4 10 1500 1000000001 5 10 2978 1000000001 6 12 1000000001 1000000001 7 2978 1000000001 1000000001 8 -1 -1 -1

### Example 0

Socks: 36 37 41 42 42 84

 Index / Pairs 1 2 0 -1 1 1 -1 4 2 0 42 3 0 1000000001 4 42 1000000001 5 -1 -1

### Example 1

Socks: 36 37 41 42 42 84

 Index / Pairs 1 2 3 0 -1 -1 42 1 -1 -1 1000000001 2 -1 42 1000000001 3 -1 1000000001 1000000001 4 42 1000000001 1000000001 5 -1 -1 -1

### Example 2

Socks: 2 2 3 3 4 4 5 5 6 6 7 7 8 8

 Index / Pairs 1 2 3 4 5 6 7 0 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 1000000001 2 -1 -1 -1 -1 -1 0 1000000001 3 -1 -1 -1 -1 -1 1000000001 1000000001 4 -1 -1 -1 -1 0 1000000001 1000000001 5 -1 -1 -1 -1 1000000001 1000000001 1000000001 6 -1 -1 -1 0 1000000001 1000000001 1000000001 7 -1 -1 -1 1000000001 1000000001 1000000001 1000000001 8 -1 -1 0 1000000001 1000000001 1000000001 1000000001 9 -1 -1 1000000001 1000000001 1000000001 1000000001 1000000001 10 -1 0 1000000001 1000000001 1000000001 1000000001 1000000001 11 -1 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 12 0 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 13 -1 -1 -1 -1 -1 -1 -1

### Example 3

Socks: 2 3 3 5 5 7 7 11 11 13 13 17 17 19

 Index / Pairs 1 2 3 4 5 6 7 0 -1 -1 -1 -1 -1 -1 4 1 -1 -1 -1 -1 -1 -1 1000000001 2 -1 -1 -1 -1 -1 4 1000000001 3 -1 -1 -1 -1 -1 1000000001 1000000001 4 -1 -1 -1 -1 4 1000000001 1000000001 5 -1 -1 -1 -1 1000000001 1000000001 1000000001 6 -1 -1 -1 4 1000000001 1000000001 1000000001 7 -1 -1 -1 1000000001 1000000001 1000000001 1000000001 8 -1 -1 4 1000000001 1000000001 1000000001 1000000001 9 -1 -1 1000000001 1000000001 1000000001 1000000001 1000000001 10 -1 4 1000000001 1000000001 1000000001 1000000001 1000000001 11 -1 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 12 2 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 13 -1 -1 -1 -1 -1 -1 -1

### Example 4

Socks: 7097711 14685971 15198493 20544910 25475624 30574577 39073007 40498239 53612697 81133258 84672537 94092596 103237637 103522060 107063881 113911604 126303054 131752569 133711906 136721027 138749191 147944789 150802600 153380496 156513984 173978710 177512688 182506778 183966551 189375153 196140741 198304613 213794688 219972874 248268555 262522458 275731772 283496852 296707007 310701088 323567404 339840186 359573809 361913171 361931892 368550363 372047868 379821990 404620563 417177802 418932836 444803289 471852627 478582453 479711181 483031419 519074050 522136404 537655880 540721924 545404205 547204602 547914047 551745921 579004999 581869303 609397213 638781100 640439653 647984700 676943010 684602223 708632712 712568903 735241235 746745228 755486970 758242872 764919655 795755685 802611721 809094427 811450930 812852787 826647953 857788837 867128744 867889991 870676136 879609715 884392679 884870761 892462744 902841101 910208077 913778155 944672732 946129058 949333986 967048445

 Index / Pairs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 13114458 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 13114458 13210155 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 13114458 13210155 13795166 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 13114458 13210155 13795166 16272782 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17464726 17714459 11 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 12 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17464726 17714459 25870453 13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 14 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17464726 17714459 25870453 28958310 15 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 16 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17464726 17714459 25870453 28958310 31140884 17 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 18 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17464726 17714459 25870453 28958310 31140884 1000000001 19 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17464726 17714459 25870453 28958310 31140884 1000000001 1000000001 21 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 22 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17464726 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 23 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 24 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17464726 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 25 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 26 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9339907 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 27 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 28 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9339907 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 29 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 30 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9339907 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 31 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 32 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9339907 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 33 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 34 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9339907 12866316 13210155 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 35 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9339907 12866316 13210155 13795166 17714459 24798573 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 36 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8741742 9339907 12866316 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 37 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9339907 12866316 13210155 13795166 17714459 24798573 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 38 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8741742 9339907 12866316 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 39 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8741742 9339907 12866316 13795166 17714459 24798573 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 40 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7774122 8741742 9339907 13795166 16272782 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 41 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7774122 8741742 9339907 13795166 17714459 24798573 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 42 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7659213 7774122 8741742 9339907 13795166 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 43 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7659213 8741742 9339907 13795166 17714459 24798573 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 44 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7659213 7774122 8741742 9339907 13795166 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 45 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7659213 8741742 9339907 13795166 17714459 24798573 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 46 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7659213 7774122 8741742 9339907 13795166 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 47 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7659213 8741742 9339907 13795166 17714459 24798573 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 48 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 49 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 50 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 25870453 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 51 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 52 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6729826 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 53 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 54 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6482706 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 55 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 56 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6482706 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 57 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 27527910 28958310 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 58 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6482706 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 59 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 27527910 28958310 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 60 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6482706 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 61 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 27527910 28958310 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 62 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6482706 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 63 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 27527910 28958310 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 64 -1 -1 -1 -1 -1 -1 -1 -1 -1 6482706 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 65 -1 -1 -1 -1 -1 -1 -1 -1 -1 7591983 7659213 8741742 9339907 13795166 17714459 27527910 28958310 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 66 -1 -1 -1 -1 -1 -1 -1 -1 6482706 7591983 7659213 8741742 9339907 13795166 17714459 28958310 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 67 -1 -1 -1 -1 -1 -1 -1 -1 6482706 7591983 7659213 8741742 9339907 13795166 17714459 28958310 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 68 -1 -1 -1 -1 -1 -1 -1 6482706 7545047 7591983 7659213 8741742 9339907 13795166 17714459 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 69 -1 -1 -1 -1 -1 -1 -1 6482706 7591983 7659213 8741742 9339907 13795166 17714459 28958310 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 70 -1 -1 -1 -1 -1 -1 3936191 6482706 7591983 7659213 8741742 9339907 13795166 17714459 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 71 -1 -1 -1 -1 -1 -1 3936191 6482706 7591983 8741742 9339907 13795166 17714459 24030489 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 72 -1 -1 -1 -1 -1 3570078 3936191 6482706 7591983 8741742 9339907 13795166 17714459 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 73 -1 -1 -1 -1 -1 3570078 6482706 7591983 8741742 9339907 13795166 17714459 22672332 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 74 -1 -1 -1 -1 2755902 3570078 6482706 7591983 8741742 9339907 13795166 17714459 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 75 -1 -1 -1 -1 2755902 3570078 6482706 7591983 8741742 9339907 13795166 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 76 -1 -1 -1 1456326 2755902 3570078 6482706 7591983 9339907 13795166 17714459 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 77 -1 -1 -1 1456326 3570078 6482706 6676783 7591983 9339907 13795166 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 78 -1 -1 1401857 1456326 3570078 6482706 7591983 9339907 13795166 17714459 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 79 -1 -1 1401857 1456326 3570078 6482706 7591983 9339907 13795166 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 80 -1 761247 1401857 1456326 3570078 6482706 7591983 9339907 17714459 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 81 -1 761247 1401857 1456326 3570078 7591983 9339907 13795166 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 82 478082 761247 1401857 1456326 3570078 7591983 9339907 17714459 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 83 478082 761247 1456326 3570078 7591983 9339907 13795166 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 84 478082 761247 1456326 3570078 7591983 9339907 17714459 31140884 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 85 478082 761247 1456326 3570078 7591983 9339907 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 86 478082 761247 1456326 3570078 7591983 10378357 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 87 478082 1456326 2786145 3570078 7591983 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 88 478082 1456326 3570078 7591983 10378357 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 89 478082 1456326 3570078 7591983 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 90 478082 1456326 3570078 10378357 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 91 1456326 3570078 7591983 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 92 1456326 3570078 10378357 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 93 1456326 3570078 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 94 1456326 3570078 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 95 1456326 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 96 1456326 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 97 3204928 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 98 17714459 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 1000000001 99 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1