Minimax exercise
Statement
Goal
Difficulty: MediumTopic: Minimax algorithm, Alpha–beta pruning, Zero-sum games, Negamax
We are given a 2-player, zero-sum game, where players alternate turns. The game always lasts D turns, and during its move, every player has to choose from B choices. Thus, D is the game tree depth, B its branching factor, and depending on players' choices, the game has B^D possible outcomes.
Assuming the game tree is small enough, we can check all outcomes and solve the game (i.e. compute the best strategy for every player) using the Minimax algorithm ( https://en.wikipedia.org/wiki/Minimax ).
To make our algorithm more efficient, we can skip some computations using the alpha-beta prunning technique ( https://en.wikipedia.org/wiki/Alpha-beta_pruning ).
Your task is to compute the minimum gain for the first player using Minimax with alpha-beta cutoffs. Moves should be examined in left-to-right order, as provided in the input.
Input
Line 1: 2 space-separated integers:
D - depth of the game tree (assuming root is depth 0)
B - the branching factor
Line 2: B^D space-separated integers - the leafs of the game tree containing scores of the first (max) player.
D - depth of the game tree (assuming root is depth 0)
B - the branching factor
Line 2: B^D space-separated integers - the leafs of the game tree containing scores of the first (max) player.
Output
Two space-separated numbers:
- the best score that the root player is guaranteed to obtain
- the number of visited tree nodes
- the best score that the root player is guaranteed to obtain
- the number of visited tree nodes
Constraints
0 < D < 15
0 < B < 15
-1000 < game score < 1000
number of leafs < 3500
0 < B < 15
-1000 < game score < 1000
number of leafs < 3500
Example
Input
1 4 2 -1 3 0
Output
3 5
Tags
Minimax
Difficulty
Medium
Test cases
Depth 1 game Test
Input
1 4
2 -1 3 0
Output
3 5
Another depth 1 game Validator
Input
1 10
0 -4 66 12 -48 22 76 0 4 77
Output
77 11
Depth 2, no cutoffs Test
Input
2 2
1 2 3 4
Output
3 7
Depth 2, no cutoffs II Validator
Input
2 3
5 3 4 6 7 2 8 9 2
Output
3 13
Depth 2, cutoffs Test
Input
2 2
1 2 0 4
Output
1 6
Depth 2, cutoffs II Validator
Input
2 3
5 3 4 2 4 9 8 2 6
Output
3 10
Small game Test
Input
3 2
-1 0 2 666 -3 -2 666 666
Output
0 11
Small game II Validator
Input
3 2
-4 5 6 -3 0 5 -2 1
Output
5 11
Slightly deeper game Test
Input
5 2
-821 -318 46 -870 -595 -56 -817 -170 -464 1 -212 67 -83 -233 -263 83 -890 -713 -141 -320 -676 93 -794 -175 -322 -481 -916 -761 91 37 -464 -194
Output
-170 37
Slightly deeper game II Validator
Input
6 2
91 -165 -480 34 -474 -328 -563 -691 -791 80 -113 -82 -440 -964 -243 -394 -883 -442 -885 -761 -181 -109 -836 -241 -600 -670 -847 -593 -492 -630 -545 -967 -531 -141 -654 -992 -400 64 90 -10 -293 -696 -458 -650 -325 -219 -120 -822 -940 -282 -252 68 -615 -584 -78 -985 -905 -425 -398 -797 -876 -117 -86 -36
Output
-615 96
Random game, deep but narrow Test
Input
11 2
19 10 83 29 64 46 79 72 63 41 10 80 51 24 1 36 27 19 -4 20 59 3 53 86 33 60 82 61 3 41 39 59 -2 6 74 85 12 95 68 60 -2 77 -4 44 -9 31 63 90 16 29 13 55 28 98 83 32 -4 27 9 -3 10 66 24 72 -1 55 79 48 87 35 48 19 3 -8 27 30 83 99 94 35 20 57 55 25 57 93 19 85 53 82 99 73 21 69 73 46 49 18 18 91 68 83 99 50 11 13 5 10 44 -2 94 85 69 -6 51 79 34 45 39 77 64 48 61 90 99 32 62 36 3 52 17 89 73 66 22 13 4 86 23 -9 18 23 65 36 10 8 93 68 22 12 12 66 65 37 31 41 54 81 18 25 49 10 94 35 42 -5 55 26 7 -6 27 90 40 70 90 28 34 22 57 60 -7 2 84 -5 26 44 57 36 15 47 47 51 60 64 35 18 61 53 19 85 21 26 29 31 8 65 54 65 68 15 94 30 56 84 88 45 74 37 63 45 12 58 74 42 -7 49 49 93 93 79 77 6 17 5 64 66 75 32 28 65 63 85 68 0 60 61 37 48 44 37 3 69 80 28 63 56 60 18 -3 40 80 44 42 5 56 84 35 43 62 11 24 98 93 48 28 86 78 -3 37 44 36 36 -5 55 -8 43 53 53 55 37 2 61 42 9 13 1 -1 -1 20 98 65 50 72 -8 88 64 -2 55 93 46 60 74 61 85 26 93 57 21 0 95 52 86 81 -8 22 55 89 5 99 98 89 17 58 -7 93 -3 30 85 23 10 24 46 67 36 91 24 32 6 9 41 65 82 48 85 37 84 80 26 3 -6 81 60 47 37 23 77 85 11 49 5 19 1 8 52 69 -8 88 81 12 75 3 -3 88 55 21 18 10 34 23 49 80 14 61 6 19 93 45 84 -6 49 1 29 90 65 -8 84 -1 26 40 81 68 57 28 6 19 41 13 16 64 68 39 40 -1 61 34 22 28 37 87 47 58 13 -5 39 75 69 36 4 94 95 27 55 20 11 27 95 27 0 95 15 41 19 29 63 91 25 40 96 39 3 80 94 0 -4 27 51 71 66 45 59 47 95 13 98 53 15 63 62 18 18 62 39 37 26 12 8 15 43 93 -5 96 37 82 18 38 81 95 51 74 64 34 81 58 61 68 15 95 70 37 83 -6 59 51 28 43 12 40 75 4 -2 28 74 32 50 6 58 72 48 77 -3 19 -7 90 51 69 95 53 88 89 53 96 95 73 27 51 -7 83 89 60 46 -2 95 26 -5 81 -2 83 45 20 61 61 42 17 12 78 3 47 71 53 95 3 -4 28 -4 31 27 54 12 60 55 38 96 58 1 -7 42 8 60 99 69 -5 42 85 11 20 80 28 37 -6 40 -9 -9 90 52 52 88 86 59 23 44 70 55 63 44 83 14 92 45 33 82 86 24 54 87 25 26 97 6 15 5 1 12 58 92 52 70 71 4 16 72 -6 16 2 -4 21 98 94 89 20 20 91 39 73 94 49 35 48 78 -3 0 68 4 18 71 53 38 3 78 44 1 74 51 22 45 66 49 34 23 67 98 72 -6 25 80 82 49 32 6 33 95 28 88 19 74 76 86 19 -5 66 92 45 36 20 68 17 1 4 58 60 -4 -1 40 66 -9 88 -7 65 96 26 -9 82 31 31 52 60 55 3 -1 55 -8 84 -5 70 73 59 93 22 83 83 83 32 50 3 18 33 24 52 49 93 36 98 26 53 72 51 -8 61 0 -4 62 93 85 33 49 30 -7 42 16 11 73 76 27 85 51 27 73 5 37 84 34 44 34 91 58 29 -4 76 95 62 55 22 98 56 67 1 37 14 91 98 16 6 58 39 99 -2 12 43 75 15 45 21 0 -8 27 2 -1 80 50 16 59 -3 17 12 15 63 59 68 -9 59 60 96 -4 7 44 3 56 4 52 16 30 -8 2 -6 5 66 -5 40 64 44 47 40 84 50 3 27 46 26 99 94 15 68 99 95 79 17 4 4 28 79 43 -1 75 50 57 6 79 98 36 46 65 30 23 19 71 48 61 8 52 62 20 75 -1 90 92 40 55 -9 63 98 43 80 2 31 13 72 58 44 -1 28 27 86 5 54 88 11 83 74 95 78 40 76 8 5 75 6 -8 72 57 48 96 78 93 78 -4 44 8 93 99 23 10 69 63 90 -9 46 1 0 74 68 88 -1 35 60 60 15 15 -2 78 63 44 49 0 61 18 52 72 17 7 41 73 14 27 27 59 48 19 15 54 93 51 77 96 33 47 71 78 71 89 24 -1 -9 3 57 95 72 59 85 50 80 58 33 99 48 -7 2 74 84 89 -4 -6 55 23 54 34 -4 31 47 97 67 74 79 7 -9 51 20 74 25 68 73 96 -9 -2 44 19 62 44 79 50 15 58 -9 15 51 77 45 87 75 14 37 91 26 62 82 48 96 93 78 22 56 65 95 65 52 40 85 82 41 15 92 86 77 6 90 43 89 89 -7 9 59 12 88 60 42 30 25 73 32 61 95 94 11 -9 37 92 46 67 52 61 76 53 54 73 92 -3 23 51 30 69 18 70 58 42 41 54 49 11 11 77 60 11 99 15 2 81 32 84 17 44 26 69 10 11 -6 98 0 98 31 91 4 72 82 63 65 4 38 29 26 16 55 78 62 47 28 37 7 81 88 85 94 56 51 78 73 40 56 32 19 83 33 32 71 97 80 66 81 61 72 98 71 68 58 84 54 91 39 92 72 83 25 16 25 55 45 29 44 75 84 20 29 49 58 59 -1 56 59 12 68 62 53 43 67 13 39 18 -7 88 2 21 91 -8 48 83 41 54 62 96 47 71 32 61 3 81 84 63 27 28 50 -1 23 9 31 10 13 31 63 23 83 84 62 -4 38 25 -2 44 65 78 82 4 83 68 79 76 83 72 49 84 81 32 72 24 69 90 20 52 48 12 75 49 92 81 23 46 50 10 33 -2 42 67 12 64 86 43 78 -2 19 28 2 79 52 12 -8 83 8 30 73 4 10 93 67 73 54 -7 5 80 4 45 18 26 24 92 33 75 21 69 24 55 6 87 6 12 51 8 71 -3 57 25 42 97 6 29 23 69 -6 -5 84 96 43 31 72 99 73 67 14 92 91 19 78 94 29 42 0 2 17 83 77 -8 26 90 22 4 77 60 47 45 19 -9 80 81 38 43 10 60 15 87 19 79 61 40 0 23 11 23 16 90 1 3 1 12 87 10 30 90 56 -6 49 55 72 64 33 18 90 27 -4 88 33 71 50 81 77 36 45 30 80 4 29 43 30 70 35 92 -7 82 60 38 69 86 -1 37 14 11 90 76 4 29 53 71 98 92 23 85 68 96 -7 -5 22 7 83 71 83 99 73 15 28 64 -9 68 86 67 29 14 38 9 16 91 37 -8 68 2 57 9 20 83 65 96 22 93 -1 73 74 70 95 4 22 44 39 97 27 42 51 29 36 61 -6 19 82 55 1 41 64 72 38 33 77 70 70 95 72 -4 2 10 84 35 14 94 36 90 -9 0 12 5 16 17 60 83 79 44 18 60 57 97 84 12 18 98 74 41 70 86 55 62 10 7 54 12 25 66 59 49 -9 67 9 70 30 61 30 99 67 49 55 20 -6 21 1 94 18 16 76 94 73 44 47 53 83 78 39 -6 7 -7 55 6 45 62 85 93 22 15 86 56 63 98 95 55 26 52 55 61 83 44 17 81 69 22 99 73 82 -7 67 96 57 6 61 62 37 31 6 61 55 35 10 98 82 36 53 29 50 95 58 53 54 72 47 43 66 83 9 29 20 99 4 20 80 55 16 17 -9 76 27 12 31 -5 23 70 58 92 76 48 -1 27 54 56 72 79 86 -6 74 33 55 83 -4 -3 48 69 22 53 -1 64 22 88 66 58 61 33 75 95 84 85 71 44 1 -1 17 33 24 24 34 82 50 73 44 93 -6 -6 17 -5 68 1 97 60 99 81 81 57 18 22 38 53 81 92 62 66 26 61 47 57 19 44 97 64 97 11 68 86 64 89 23 75 29 -4 35 96 49 85 11 77 59 8 88 -9 6 1 -1 14 55 78 57 78 99 53 45 34 74 78 63 70 32 82 -7 11 -9 78 98 9 45 97 41 35 30 90 14 50 72 34 63 3 35 -2 -5 34 29 55 83 90 53 73 87 15 -8 88 -2 3 94 47 99 81 17 23 71 62 8 94 49 72 6 -9 23 44 60 39 60 54 -4 24 2 40 9 26 3 83 39 18 -1 31 38 81 63 39 -5 70 99 80 6 -8 -1 82 48 15 87 85 25 4 57 54 49 86 92 98 63 77 42 50 45 44 74 2 95 72 6 85 12 71 38 80 36 27 50 21 86 87 11 80 69 71 58 5 97 99 65 62 38 -1 82 89 86 0 25 37 52 19 12 88 63 72 74 89 72 84 38 26 98 -6 13 99 25 92 62 53 20 32 76 44 43 89 97 47 19 69 28 30 78 16 73 67 13 40 28 -9 86 56 2 16 25 92 25 -2 78 6 58 93 -9 -5 33 -9 99 1 30 3 -1 93 -7 12 40 16 66 18 35 -9 77 34 45 41 77 23 63 15 69 48 20 93 56 89 65 51 99 41 76 39 14 2 97 91 71 88 56 0 61 14 53 16 0 94 40 64 72 72 40 53 49 35 37 97 63 -2 75 33 55 87 10 48 52 71 36 88 87 31 48 42 11 92 32 74 75 13 26 85 11 59 75 68
Output
59 1510
Random game, shallow but wide Validator
Input
3 14
48 7 99 36 9 78 72 -8 4 80 5 85 42 77 -5 19 97 9 12 41 82 99 67 0 48 95 63 87 0 41 59 -4 79 60 86 30 11 -2 43 87 42 -3 1 32 74 72 11 28 47 50 93 -8 40 40 44 5 53 83 37 20 83 99 18 4 33 41 89 84 5 38 64 77 37 53 52 40 94 44 5 79 79 98 78 41 11 71 40 29 82 38 87 56 59 48 11 25 73 52 -2 76 95 75 73 12 12 76 41 40 74 74 11 31 -6 74 17 90 26 9 -5 -6 61 85 63 70 6 91 8 44 -7 95 82 70 23 76 82 97 52 61 63 -5 89 94 15 78 31 0 62 2 85 -3 28 47 82 24 50 40 -4 98 76 79 69 27 0 15 68 -8 31 6 56 31 -1 54 86 -1 93 73 6 80 -6 24 52 25 73 77 11 99 93 53 -5 69 63 79 77 66 20 35 -5 -4 -7 72 6 -3 9 7 6 20 44 -7 6 21 28 99 40 11 55 60 30 30 55 93 2 57 10 92 24 92 8 16 98 61 88 88 65 14 -4 6 35 -7 44 65 64 84 42 66 26 77 96 51 37 93 27 20 70 50 27 11 12 36 37 25 84 48 93 68 19 27 -3 57 73 90 16 44 54 34 45 44 25 31 22 4 77 78 -1 51 36 60 2 28 65 42 96 55 23 3 71 34 35 58 73 71 23 29 26 93 50 45 11 95 90 97 19 54 91 5 9 63 76 62 92 81 27 13 86 12 94 24 97 99 32 29 96 63 62 17 -4 9 -1 37 62 61 89 87 -4 1 77 45 84 -5 15 21 70 19 17 36 34 22 48 -9 98 19 69 99 18 50 12 71 2 54 -3 12 28 8 66 90 39 20 38 74 40 69 79 54 12 7 95 47 38 96 31 11 50 -2 81 96 -8 85 23 37 97 54 79 47 63 96 -2 76 99 44 18 22 11 -1 70 13 26 27 -6 24 40 0 8 11 8 35 96 64 45 4 58 56 5 28 22 94 78 90 26 37 60 -1 65 2 47 83 20 52 51 -3 24 -3 84 -5 91 49 46 51 14 94 22 60 8 36 90 99 83 88 21 55 75 13 36 31 67 99 24 92 43 -3 79 4 54 25 33 40 0 27 85 18 49 39 70 55 65 95 24 94 29 -3 97 30 84 98 12 83 74 25 77 27 89 71 75 68 13 0 71 73 52 99 3 16 79 26 94 -2 34 52 -3 17 95 31 9 69 -7 37 86 16 84 84 74 34 75 -8 78 24 45 86 15 36 -8 28 80 5 -6 18 -4 49 66 50 14 1 13 67 79 45 81 23 98 90 64 63 81 4 95 92 24 7 74 31 27 68 69 46 53 78 12 71 -4 81 15 98 11 89 4 13 54 78 94 6 80 24 -6 13 56 39 83 64 66 88 52 17 7 23 77 68 12 52 31 11 25 87 25 18 80 74 -3 5 24 -1 47 -4 29 74 58 86 67 48 36 17 4 33 4 2 59 55 81 31 77 34 64 48 61 49 79 36 67 82 57 98 55 85 96 -4 25 51 39 63 21 12 11 92 60 12 50 38 6 6 59 50 69 62 64 -4 88 97 70 50 28 69 3 -4 17 -7 42 66 57 93 76 77 39 77 -3 72 52 61 47 89 75 38 29 1 7 -6 79 85 39 86 12 49 99 0 35 98 64 95 74 20 84 57 99 76 55 6 20 17 -7 -4 49 38 61 72 99 20 3 -1 6 12 89 75 7 69 56 57 37 77 11 55 0 83 80 86 18 0 60 65 73 24 49 19 40 26 47 4 75 6 76 33 31 74 19 11 85 30 49 30 11 75 65 17 39 -1 13 2 1 97 56 70 7 87 60 96 62 1 33 65 87 -1 23 -6 19 74 62 -1 81 61 1 20 36 87 65 83 13 14 55 -1 65 4 94 4 -8 77 42 41 41 74 42 32 34 12 50 5 -2 2 46 44 74 17 46 56 -5 23 80 96 90 59 73 99 18 34 68 45 32 22 -5 13 82 30 89 6 26 27 91 4 66 59 13 82 81 79 5 28 27 51 12 75 79 34 24 54 83 81 39 33 75 48 66 50 -3 25 -8 17 56 41 71 17 95 55 99 26 39 55 37 39 51 32 9 43 42 35 96 25 72 3 43 8 5 18 37 34 73 27 27 69 89 36 73 35 27 9 -1 20 98 11 69 52 34 93 -6 92 90 8 28 53 23 21 4 78 22 60 7 12 66 54 -6 30 80 56 48 50 60 12 52 6 68 61 61 76 86 27 49 7 5 25 44 12 79 52 45 46 79 42 50 80 6 97 88 86 4 91 84 -7 65 68 14 52 15 47 5 11 10 78 96 61 75 37 70 41 52 73 7 3 4 24 39 98 29 42 92 57 59 39 11 82 98 70 -6 96 65 60 30 26 84 4 13 74 -8 67 -5 23 37 90 58 61 14 -7 85 40 -9 62 80 25 0 70 60 29 15 52 51 40 92 44 56 78 59 87 14 54 89 62 46 12 25 39 54 77 22 41 20 -2 24 93 92 -9 76 89 84 66 32 64 -6 8 -3 94 83 69 -7 95 -7 30 93 32 80 46 66 27 73 89 53 53 88 40 61 -5 32 26 95 67 79 39 -1 0 11 7 98 80 80 13 87 79 7 13 25 18 31 15 71 92 29 79 59 8 76 73 79 48 34 45 95 92 25 45 18 37 89 82 77 75 39 52 21 49 0 78 24 62 90 55 93 6 -7 76 22 37 34 76 64 87 -6 70 40 31 61 25 29 54 38 72 6 81 50 -7 86 39 51 95 86 -7 31 -4 18 21 65 72 84 60 55 1 -2 69 33 29 96 1 19 22 35 15 18 40 29 9 -4 73 21 5 61 25 45 48 14 41 2 55 36 20 81 99 65 4 7 76 -6 47 94 25 44 83 0 19 10 84 9 54 59 53 65 24 65 89 90 36 47 78 -2 38 17 46 33 60 63 56 61 73 75 6 89 -3 76 73 45 -7 54 76 18 32 98 3 48 62 79 24 -9 80 35 12 76 2 86 42 40 57 38 69 1 52 57 18 35 95 6 74 48 21 22 57 25 92 -8 62 81 92 10 92 18 85 48 82 21 53 34 75 89 58 6 61 81 52 5 9 94 90 44 -7 88 19 21 17 36 55 7 11 57 43 43 91 82 24 80 73 48 88 56 16 10 63 41 10 14 15 44 51 87 75 6 86 80 2 60 63 85 -2 -2 7 28 20 56 -5 21 74 43 4 4 15 62 18 42 6 34 10 32 41 83 46 16 92 27 34 99 27 81 18 66 85 72 25 28 16 2 46 58 41 -2 15 12 91 9 -5 81 72 96 89 72 10 43 15 -9 -2 84 63 67 49 42 62 42 88 -9 15 -2 78 78 87 51 48 53 37 34 35 69 78 96 38 66 78 28 81 43 30 71 96 59 -1 72 1 20 49 88 87 29 94 94 61 38 1 59 89 61 60 37 42 57 35 13 66 10 -4 10 11 66 39 78 65 56 66 -4 20 17 44 4 37 55 74 85 71 38 56 70 -3 69 47 11 82 14 90 59 85 21 37 4 11 16 32 75 64 87 -4 8 43 89 30 26 23 9 93 32 30 47 5 42 19 27 56 61 44 89 47 28 -2 11 87 15 88 32 -5 58 55 35 92 43 55 8 85 51 -5 49 1 15 77 15 91 -9 86 75 99 44 5 90 37 1 58 93 60 93 30 84 74 72 77 88 1 14 63 75 72 76 76 -9 91 78 43 35 45 10 11 67 87 49 8 36 63 47 91 83 40 39 3 94 74 81 90 1 22 56 94 59 -6 -5 -9 18 52 -9 30 47 63 79 78 56 6 37 43 4 97 29 96 30 78 90 89 93 17 22 5 33 83 91 20 -5 26 69 51 55 16 45 19 69 35 49 34 1 2 44 -8 13 78 24 77 64 13 41 72 87 20 83 67 65 18 -9 5 31 91 79 35 55 0 70 23 51 32 85 98 54 -2 44 23 -8 18 83 4 7 20 41 61 27 -5 31 -9 8 1 72 -5 50 80 35 48 14 89 32 29 23 91 11 53 85 54 0 53 78 4 83 94 73 85 78 82 -9 20 85 87 34 16 90 19 91 41 71 1 80 19 32 85 22 59 47 11 85 18 35 11 68 -2 27 65 32 80 37 69 24 54 60 83 27 47 6 14 8 -2 73 70 48 32 -8 68 72 87 90 -6 87 81 76 22 87 85 23 -9 0 30 2 13 52 73 93 41 60 40 17 31 28 89 -1 18 7 46 25 73 29 75 67 73 40 -4 29 84 35 24 62 22 81 37 18 -8 64 55 79 -8 28 -9 34 64 15 4 45 73 21 23 90 95 68 14 79 50 94 93 63 98 13 74 10 77 74 10 -9 16 -8 53 96 29 71 7 45 -4 61 21 -4 18 19 71 6 -4 48 60 43 25 22 66 9 60 34 25 66 78 69 14 22 5 15 -6 -8 94 2 6 43 91 2 81 77 64 1 78 71 87 93 6 29 12 92 91 95 -7 73 92 84 14 34 57 35 36 98 80 86 55 44 74 98 12 77 16 28 97 8 34 7 58 23 23 54 4 89 -2 94 32 27 26 -8 -2 21 27 48 3 -7 89 14 45 65 0 24 95 99 83 73 -5 17 46 67 2 13 98 49 48 49 98 -4 71 38 80 42 12 -7 2 -2 23 48 0 97 2 94 77 88 61 -8 56 52 72 47 0 24 91 18 -1 56 5 62 77 92 28 9 42 55 54 40 77 67 63 67 56 79 96 50 66 65 74 51 11 47 97 15 52 76 36 63 28 25 55 -1 82 51 31 7 11 84 55 98 71 15 35 64 41 68 23 -5 26 56 -3 31 48 20 84 27 92 76 37 65 96 5 79 89 70 74 -7 71 27 53 38 36 62 34 32 90 68 -7 2 60 39 32 76 -6 57 43 84 15 13 69 81 82 12 69 28 26 12 6 13 12 29 31 63 1 49 73 95 59 4 74 85 29 94 70 77 44 34 24 54 26 80 36 50 56 -3 61 41 21 99 99 97 96 1 69 23 70 9 64 62 -6 27 51 35 6 65 17 13 -1 11 -3 98 47 58 81 33 24 89 34 26 83 75 46 98 -3 23 21 91 21 64 38 89 85 80 77 71 20 14 31 26 -8 -5 36 91 30 75 87 -3 78 9 55 32 98 78 55 4 42 83 49 22 61 2 95 67 52 34 73 -3 94 58 43 93 98 -8 22 42 8 50 54 36 5 20 56 87 37 69 10 46 13 35 51 68 -9 87 66 84 18 67 -1 36 24 67 17 -4 37 45 46 22 32 -4 17 30 82 27 97 4 -8 69 -3 16 48 56 51 17 -7 83 54 68 79 17 37 19 14 39 65 -9 23 67 -8 67 48 98 70 96 15 95 51 54 37 11 64 72 91 57 47 90 54 8 53 31 9 25 9 25 36 27 46 15 45 21 91 42 12 -5 -5 32 92 77 61 25 41 59 96 99 42 46 64 72 61 3 49 64 -5 13 16 96 25 97 59 22 63 -2 31 24 2 68 31 25 9 96 91 6 36 21 1 40 48 57 52 20 89 14 80 32 33 32 70 -1 32 49 4 45 79 35 87 9 22 27 26 5 56 15 78 28 62 41 -1 12 -2 29 48 88 14 67 56 88 -3 21 11 59 69 98 19 11 51 38 -7 65 20 34 77 49 35 8 76 80 -7 22 83 35 54 48 61 55 0 12 53 90 0 80 44 11 11 20 28 72 59 24 35 -5 -8 10 98 48 32 50 52 43 7 61 77 41 48 3 67 25 56 96 51 78 -7 85 68 90 77 28 13 15 10 -1 67 36 83 53 65 2 60 81 26 67 96 7 50 -6 24 75 50 93 7 82 73 33 39 7 88 39 24 65 84 13 75 97 87 -6 93 98 34 50 71 80 14 97 34 86 59 20 51 45 7 78 52 60 35 81 86 27 73 96 11 42 42 73 17 11 5 50 80 29 54 55 96 -4 98 31 66 11 39 1 60 81 84 14 6 99 87 28 3 63 7 31 -9 25 50 67 84 80 -4 74 6 2 65 72 -9 61 84 74 85 86 34 57 86 76 96 27 10 32 22 -1 44 34 32 74 13 95 32 78 59 2 70 51 -3 4 89 36 96 69 50 51 82 84 61 93 67 45 88 27 77 4 88 11 73 45 75 43 28 38 82 52 88 35 28 -3 24 91 38 12 30 67 47 -7 25 55 19 37 15 50 22 3 25 33 60 67 49 36 52 74 15 98 38 78 51 17 51 28 13 12 22 15 25 42 38 6 70 10 9 47 17 -4 48 -4 32 93 73 28 36 0 2 20 79 74 12 66 2 23 57 8 83 -1 92 23 58 97 34 24 53 79
Output
87 871
Another large random game Test
Input
5 5
30 41 95 -7 11 28 53 47 62 81 10 73 63 -3 34 55 95 68 89 -4 16 95 28 92 41 5 49 43 19 25 28 42 52 19 90 60 3 0 -6 30 32 35 84 10 27 48 95 61 79 58 21 28 5 -9 92 4 83 94 21 83 66 91 31 90 67 86 39 1 2 0 67 34 -1 2 37 43 -1 94 -2 33 80 42 3 26 50 39 91 12 -1 56 87 46 67 46 45 75 45 2 61 90 4 40 -6 13 25 85 6 8 29 30 12 60 -9 37 5 34 41 25 45 94 51 -4 -9 0 81 17 54 92 66 -5 10 31 -8 81 15 83 19 36 10 34 5 77 41 12 31 15 69 -3 19 10 13 67 -4 69 39 81 49 27 82 58 8 22 11 82 13 36 90 72 -3 71 9 10 83 30 29 44 22 88 63 26 49 -8 20 88 83 -2 12 98 24 -6 22 59 49 72 1 13 42 72 47 -4 25 6 84 97 76 80 51 21 55 25 59 -6 90 13 26 3 99 -2 50 28 66 88 72 68 98 9 20 85 8 84 70 38 13 36 39 96 26 44 -4 44 8 97 2 21 35 20 48 4 32 86 11 58 43 64 17 78 -3 58 10 57 50 -5 19 53 54 35 47 72 4 13 95 58 3 54 27 53 84 -8 46 28 37 75 96 16 63 12 -6 60 -8 69 93 49 94 82 61 46 29 77 -9 36 2 44 46 2 34 52 21 82 9 -7 17 10 54 28 16 47 12 66 11 2 41 32 21 93 27 -5 12 27 26 94 -7 25 60 58 1 8 50 0 26 56 35 76 27 42 8 31 43 77 60 21 82 75 81 8 -1 8 20 -6 28 33 -4 15 -4 94 24 86 32 76 59 31 13 1 40 88 46 -9 53 2 93 45 77 -2 62 86 2 67 0 90 13 24 35 91 86 87 65 79 -6 50 67 83 95 86 36 22 -4 28 -6 2 -9 65 90 21 21 15 -9 23 97 12 79 4 77 36 70 31 68 57 2 43 24 29 61 48 80 47 29 53 50 28 89 98 5 39 43 2 17 82 67 29 51 2 85 73 77 63 29 27 22 89 16 25 69 5 85 86 77 11 28 67 62 1 96 91 99 80 -8 85 63 94 50 16 28 14 38 21 34 79 11 23 72 5 87 92 35 66 9 26 49 12 79 98 83 66 -9 86 14 66 24 15 62 19 49 59 41 -5 91 67 63 40 89 92 19 92 7 77 61 -6 4 88 48 -1 42 62 68 26 49 58 25 51 55 44 11 -6 83 15 24 24 47 30 70 51 12 36 65 26 53 86 -7 51 91 38 61 31 -7 14 20 60 25 18 67 0 19 76 25 42 84 19 44 84 68 34 78 36 85 1 49 11 93 31 55 51 36 23 40 86 43 8 82 35 93 1 40 15 13 29 84 99 74 82 91 48 98 52 76 17 73 43 -7 -8 74 -3 19 51 47 57 2 77 7 41 99 18 37 14 30 29 95 50 89 27 70 4 30 48 12 51 61 33 29 89 -7 0 79 43 52 24 26 -8 94 20 32 98 72 27 8 -8 97 72 36 28 4 67 9 62 -8 61 16 2 8 43 29 52 86 83 -9 31 10 89 7 37 95 74 65 0 48 -6 99 84 73 31 51 -2 91 -4 39 86 20 40 54 20 47 11 57 80 53 22 41 81 33 3 -6 79 41 13 36 83 30 8 39 51 23 17 86 62 83 64 64 59 64 87 51 46 13 -9 95 98 43 1 47 89 87 13 -4 93 -6 22 30 48 51 55 76 4 40 -6 93 48 68 62 -3 0 66 32 92 96 -6 89 35 23 95 6 91 20 13 22 10 79 38 18 32 28 29 91 92 67 38 70 91 64 28 2 -9 39 40 83 50 52 23 8 21 6 63 25 72 44 25 32 11 82 49 13 -5 16 15 60 4 -5 11 20 94 58 75 56 71 53 -9 91 87 96 7 3 26 41 84 60 70 84 56 4 26 99 1 48 92 19 20 -7 88 96 98 -6 14 -2 53 44 93 74 43 91 60 78 77 33 64 83 8 59 18 94 50 62 50 51 41 21 67 88 3 80 38 81 45 74 99 22 46 50 28 82 12 51 11 55 31 98 5 95 74 68 73 35 87 26 90 63 26 -7 51 93 29 93 15 72 53 16 47 -7 1 33 -2 89 74 28 28 3 26 37 10 10 23 81 15 41 8 25 23 58 -2 35 64 42 38 5 61 51 63 5 27 65 67 14 91 -7 90 11 92 14 56 63 13 15 32 -5 79 30 32 98 54 8 79 69 80 5 7 42 98 -1 41 95 83 52 1 64 71 7 37 21 63 84 33 8 99 29 28 42 34 40 -6 58 75 81 23 67 16 -8 58 65 38 60 83 72 46 28 26 29 7 23 43 28 25 77 93 61 62 75 26 8 72 37 61 29 94 35 16 39 20 98 61 82 92 56 20 64 42 79 80 5 95 85 14 94 73 61 10 51 55 4 57 68 5 28 71 57 -3 35 79 85 8 82 59 78 11 11 54 79 31 68 86 1 8 14 8 -4 36 50 69 22 5 74 -5 -8 63 13 89 88 6 4 94 27 16 52 8 92 86 -1 91 43 29 73 85 -6 57 80 61 98 10 84 0 62 -1 96 75 18 1 30 36 77 64 72 56 30 71 50 89 -4 48 -8 -4 19 83 46 61 86 84 82 60 99 79 88 66 -1 22 76 55 79 99 9 97 60 29 33 2 1 47 68 12 59 11 14 61 32 47 20 88 96 32 92 -5 9 1 69 68 94 65 59 14 51 33 6 68 20 92 81 17 84 70 6 31 98 0 40 20 -7 29 40 60 94 39 55 3 16 5 18 3 82 80 88 -5 5 41 69 16 52 92 19 11 56 62 14 45 39 8 13 48 40 6 96 41 88 80 20 67 58 28 35 33 59 46 70 42 86 94 58 41 83 -4 51 45 35 67 16 96 50 35 58 38 -1 15 15 64 68 5 49 94 48 24 -9 36 88 21 17 42 -2 83 74 82 10 86 35 39 86 33 46 51 -7 60 81 94 18 -7 -4 1 67 -4 12 70 87 53 38 33 0 16 66 29 -9 -8 -5 63 -7 6 36 63 52 75 47 80 -2 14 92 91 89 -1 54 43 -9 51 25 45 41 87 91 65 57 99 71 3 66 12 69 83 81 90 -5 98 59 -9 24 2 -3 95 24 91 32 26 84 34 92 58 28 85 56 5 37 33 73 15 -7 60 16 3 45 -4 11 14 42 67 98 98 78 68 63 11 99 53 69 29 62 -9 32 1 75 20 36 39 59 6 12 13 65 79 21 73 51 22 94 49 27 53 38 4 53 74 66 55 -4 64 -9 86 42 46 56 83 43 75 -5 33 91 93 75 19 2 49 61 43 27 38 55 65 98 33 12 27 6 -2 -6 45 -4 64 10 29 77 21 4 -3 62 64 7 83 63 68 32 41 14 21 34 99 84 59 -2 57 63 72 88 57 9 74 92 1 91 83 50 17 -1 23 18 26 80 73 83 0 24 59 5 15 92 26 44 78 69 56 46 58 -2 38 1 87 48 84 96 36 -1 -5 87 27 4 51 88 94 31 85 44 41 19 44 17 57 64 29 8 13 66 60 55 3 35 -4 16 60 77 67 58 64 78 -1 48 68 33 72 48 98 28 22 16 77 93 -8 19 27 -2 17 64 44 84 13 46 21 62 -3 49 64 25 45 6 45 76 -4 58 88 37 36 89 36 52 86 13 69 60 69 26 2 -5 48 69 -1 34 47 15 25 64 77 38 44 19 81 58 8 75 93 84 40 40 88 57 2 61 73 2 91 80 26 76 11 14 72 70 89 38 22 88 -8 83 5 29 60 52 43 73 88 26 47 64 52 86 20 97 50 54 51 73 82 2 77 47 48 59 36 33 76 12 95 24 67 28 96 71 4 60 41 33 28 8 29 54 95 48 14 88 -3 -4 74 24 48 69 79 79 24 80 92 -5 27 80 9 60 24 -9 -8 76 27 -5 22 92 10 63 63 61 12 38 67 64 61 45 -7 95 -4 33 95 83 82 42 80 65 36 53 44 0 -3 81 45 30 15 44 90 6 15 22 66 1 43 96 12 -8 -1 97 -4 -8 65 89 28 24 30 79 71 96 73 98 78 95 95 0 22 42 10 34 71 67 -1 14 73 31 89 73 85 77 30 96 47 95 1 13 19 72 -5 -4 -7 57 2 1 77 18 74 53 23 -4 28 29 43 -9 91 8 92 80 30 67 69 7 81 59 29 96 18 19 83 98 11 48 51 54 6 37 49 88 57 58 66 61 60 46 33 98 3 35 30 46 -3 -9 34 12 24 90 19 73 13 17 4 14 12 72 87 36 71 63 13 33 7 74 4 92 23 26 51 17 25 16 56 41 77 48 48 44 15 98 23 78 39 78 67 92 24 32 18 88 83 16 58 36 52 55 58 74 67 28 1 99 61 23 26 15 76 17 7 47 4 -9 1 53 94 48 55 90 40 54 -3 56 28 99 25 96 78 -5 11 49 96 -4 55 41 17 89 40 28 41 85 14 93 35 15 20 76 53 5 39 33 56 63 58 64 20 7 41 79 43 -5 63 38 -8 -1 95 93 -7 -7 12 65 98 23 12 90 70 0 33 36 67 70 17 94 0 83 70 73 15 76 83 48 55 64 3 5 75 74 33 13 56 68 11 53 43 32 73 33 40 74 35 6 10 26 10 44 -6 42 16 39 30 78 75 16 77 -7 35 40 6 87 73 97 0 4 33 48 73 73 12 57 70 14 67 74 69 -1 -7 1 51 80 42 21 67 6 43 51 90 -4 95 70 -5 6 55 48 81 3 63 89 30 24 95 67 9 13 3 0 47 -9 34 12 55 27 70 25 55 -5 14 71 10 51 98 12 88 93 41 76 2 81 22 65 59 4 6 85 -9 48 52 8 22 44 18 51 94 95 69 85 54 90 18 47 11 42 -6 77 20 37 95 46 -3 92 84 52 3 46 20 18 44 57 32 78 57 67 65 62 96 27 23 15 99 86 39 95 77 64 11 34 63 52 2 23 51 30 40 27 6 79 64 0 27 30 43 83 75 66 61 -3 40 97 41 18 11 27 84 96 -7 43 61 77 36 -3 3 5 31 31 47 98 4 69 58 92 25 31 89 98 66 70 84 88 82 12 96 94 41 18 11 18 97 32 46 88 31 68 -1 97 22 15 26 25 78 10 2 88 94 28 93 35 87 75 69 23 44 35 84 -5 61 53 99 62 59 16 63 -9 40 21 83 51 58 14 20 49 74 29 79 80 61 5 42 61 5 13 31 55 41 11 26 28 87 17 53 2 93 71 23 81 20 83 17 71 50 53 87 39 -5 21 15 46 42 20 64 99 30 -6 4 18 24 32 59 93 70 66 -1 2 85 79 44 15 8 77 42 -9 54 8 95 61 -5 5 18 56 15 93 58 20 52 31 98 11 12 37 26 51 55 -8 20 6 38 34 34 73 82 26 8 64 11 -1 34 19 79 -7 44 31 18 74 90 77 66 33 8 97 92 76 35 74 62 58 70 14 90 50 74 42 80 39 35 32 65 83 -8 92 72 79 75 27 94 7 96 79 93 62 28 -7 41 82 56 63 24 76 35 7 4 43 21 54 98 86 30 47 0 4 23 48 56 25 72 7 54 92 -5 61 87 90 65 49 -2 79 3 -4 -3 30 77 61 70 80 28 29 23 10 49 40 52 50 4 56 55 78 71 -2 30 7 73 44 16 56 43 49 47 41 -4 47 86 51 19 26 49 93 74 52 97 46 -3 57 83 96 29 27 1 95 57 -8 -2 1 61 85 26 95 38 3 48 38 60 36 53 22 23 59 86 13 -9 35 91 6 9 45 13 88 2 46 32 94 23 94 46 95 9 76 47 69 60 76 73 -8 15 44 52 73 93 62 89 96 71 82 75 1 25 19 33 70 29 73 3 9 44 45 64 46 89 92 35 19 33 23 8 42 5 31 57 78 72 -1 35 83 99 93 -5 -4 71 54 98 54 85 3 57 11 66 39 96 98 12 41 55 36 86 30 32 23 81 17 43 67 86 94 47 84 61 61 86 21 63 73 63 -1 85 29 27 77 50 14 11 78 33 52 34 24 55 70 45 -3 15 13 28 89 52 81 15 17 39 92 27 3 89 76 5 6 13 82 61 22 36 90 15 15 23 47 39 69 78 53 4 32 57 75 72 45 61 8 72 67 70 16 0 -8 85 -4 79 87 30 37 81 65 57 6 97 -7 94 26 65 29 36 8 31 15 61 19 8 85 24 47 86 -3 30 54 92 91 66 9 21 74 -3 30 6 -1 63 89 32 91 13 23 22 67 52 15 89 87 83 76 18 44 90 18 38 13 84 27 94 94 94 1 97 67 27 66 16 41 96 34 89 63 18 19 33 43 36 71 16 35 60 57 97 98 93 85 41 10 63 42 57 -1 -8 37 32 27 52 83 53 57 16 30 24 87 10 19 11 86 56 12 75 78 19 54 75 16 57 34 81 61 65 5 8 72 87 8 10 66 44 9 45 3 56 84 33 85 91 12 69 38 95 18 58 32 -8 40 81 4 13 12 29 -6 67 7 80 -1 85 75 94 23 7 42 22 93 -6 83 19 18 79 82 92 87 92 42 38 14 20 2 40 84 96 83 64 17 -1 27 88 73 42 89 92 38 26 71 1 86 83 87 92 68 26 30 31 89 56 60 -1 25 70 88 40 50 36 42 83 53 23 82 68 48 -2 37 9 27 29 37 -1 49 97 5 29 89 33 12 27 48 -5 59 36 91 9 52 85 -6 70 85 64 86 21 5 76 67 17 40 5 62 71 46 5 70 95 60 46 30 81 82 54 64 25 2 47 81 69 71 -4 59 89 75 25 50 81 -4 6 -9 12 -3 14 97 26 7 16 82 10 31 28 22 3 83 5 7 31 32 98 37 72 33 77 68 24 18 40 34 35 2 57 99 50 15 46 67 57 32 17 92 4 32 54 60 83 66 89 46 68 95 64 25 88 88 85 -8 -2 82 20 12 12 63 -8 99 22 -5 74 48 9 54 88 57 23 82 63 61 19 43 22 75 72 31 89 99 26 3 31 56 33 15 29 92 47 9 81 20 56 86 18 55 3 23 97 57 92 40 24 61 39 70 -9 41 43 52 24 32 8 57 -2 97 85 36 86 52 0 21 95 90 17 74 18 15 87 99 19 99 81 66 60 5 11 70 0 20 72 -4 16 68 71 -2 90 24 88 81 28 -7 45 39 37 76 10
Output
78 1119
Yet another large random game Validator
Input
5 5
77 99 86 92 38 84 97 48 32 90 39 6 49 36 8 18 31 56 60 68 94 10 34 39 58 99 54 19 34 50 70 67 87 88 27 65 92 34 30 57 21 -8 18 -6 19 -7 86 45 44 71 12 36 6 82 84 11 52 -1 44 62 3 84 22 81 68 58 69 14 39 0 54 66 67 53 35 43 42 21 78 59 48 71 71 14 42 60 64 70 56 26 65 59 98 16 76 22 70 71 93 74 68 73 42 82 87 26 83 24 46 8 30 -7 80 85 67 78 31 72 17 72 90 92 88 76 -9 61 50 71 0 5 84 92 96 56 1 86 55 1 4 86 7 83 83 35 33 59 31 99 2 39 20 11 52 77 -1 91 19 29 -9 -9 -2 -4 91 36 56 61 51 3 57 15 97 24 40 24 17 59 18 87 -8 58 28 29 40 20 34 -9 -7 -2 63 47 -1 59 43 23 56 -7 14 58 14 77 52 7 -7 86 84 2 89 33 19 49 33 -6 27 74 90 40 7 18 1 52 23 83 86 82 50 40 73 11 5 35 28 63 88 37 39 61 7 81 68 58 51 39 86 34 61 -8 4 14 6 40 46 12 37 20 99 53 9 44 46 37 6 69 46 -5 9 82 80 53 25 37 41 7 37 5 81 14 55 30 69 0 -4 59 6 -7 35 50 17 69 23 58 71 36 58 92 17 51 42 42 59 48 10 32 12 19 68 18 20 5 23 -9 67 97 63 57 42 43 60 5 67 51 -8 51 86 71 70 96 -2 83 10 0 44 30 96 85 52 22 35 89 74 80 97 91 97 43 27 7 92 41 17 7 21 94 91 41 57 89 39 50 30 16 83 66 23 59 73 72 12 32 12 24 24 41 73 12 -9 54 30 81 -3 62 6 59 48 38 10 40 93 15 33 1 52 -6 20 95 88 48 80 86 2 -7 37 11 32 9 17 17 33 45 29 -2 37 71 39 19 99 80 -5 86 27 76 71 97 86 49 90 -3 89 21 89 34 14 86 -2 71 77 71 8 26 7 -5 55 60 22 81 20 96 89 71 49 50 2 1 -4 43 63 85 89 50 53 59 98 -2 31 66 49 96 52 -5 22 70 93 99 -7 55 77 68 73 70 37 77 55 27 19 53 -8 6 79 15 32 78 85 74 79 33 53 16 84 45 87 61 41 2 79 87 30 -7 34 18 97 -8 99 33 10 55 20 31 94 61 89 97 52 63 18 13 14 62 11 3 44 84 55 76 85 56 89 12 69 90 19 15 -9 51 81 30 53 98 35 27 5 23 54 10 63 95 90 96 7 44 66 94 52 70 45 18 62 67 69 57 45 92 98 85 16 22 57 83 92 58 65 -5 5 10 68 0 38 67 42 -7 68 -7 57 54 39 -4 36 67 66 15 73 78 -8 69 36 15 58 34 89 41 62 76 27 23 80 82 45 3 90 89 44 -8 44 95 59 56 5 19 78 53 58 56 77 75 -7 90 30 24 39 75 30 40 22 26 72 2 93 79 63 28 94 9 7 31 -4 29 11 3 0 69 1 0 51 -7 17 55 33 49 34 31 -1 20 0 39 54 33 88 71 85 23 74 18 87 23 20 61 45 50 43 51 61 71 79 49 76 -2 37 -8 -8 79 92 68 32 27 4 -8 51 3 58 93 71 0 13 92 94 42 74 54 6 30 98 29 65 17 15 43 40 31 72 46 52 -8 58 58 15 38 11 -2 49 84 29 32 68 97 20 8 56 24 8 43 52 21 -1 23 45 -2 39 -5 88 -3 44 98 33 67 29 24 76 75 86 90 -7 14 44 84 75 84 69 55 16 22 91 19 11 43 39 87 22 15 11 -5 16 42 35 51 16 89 4 23 75 9 1 73 38 15 -7 58 23 50 12 93 13 81 49 74 71 81 84 89 -5 24 80 84 56 -3 52 76 8 51 26 -2 80 79 29 53 81 23 96 76 44 47 15 77 89 28 9 79 2 10 28 94 38 78 3 14 10 80 29 86 86 95 17 94 84 35 44 92 80 34 72 99 80 73 29 46 93 99 32 7 23 84 78 96 19 66 13 28 89 48 64 16 21 92 26 59 30 26 69 64 52 10 59 3 25 73 6 52 67 36 15 88 -1 73 14 50 39 59 65 78 95 99 95 84 60 99 19 6 -7 24 6 95 -3 51 62 16 97 61 6 15 48 -5 60 89 95 40 -7 99 -9 76 6 33 56 21 6 97 16 -7 65 44 45 31 70 78 63 33 89 1 69 44 52 38 18 27 65 58 87 92 -8 35 86 59 90 4 89 -4 10 74 95 57 22 66 22 93 72 8 46 37 0 37 49 63 71 56 74 78 93 95 93 37 60 31 13 2 35 56 40 39 52 35 95 78 64 79 22 26 62 75 21 -5 21 33 43 16 44 47 -4 85 25 12 46 59 75 17 98 61 68 15 27 -7 77 5 7 64 52 81 7 44 27 81 98 94 56 89 11 73 12 1 17 -2 75 29 95 66 22 60 -1 69 17 13 14 22 47 99 9 50 95 2 11 87 81 49 97 92 38 48 45 7 39 -7 24 -5 -9 -6 74 43 59 66 76 60 38 28 22 25 17 18 85 -4 28 89 99 76 46 80 7 23 32 69 93 54 59 50 76 71 84 78 35 17 11 49 21 67 83 66 65 41 52 5 28 79 88 74 34 5 87 87 37 17 97 41 29 35 85 -1 63 41 42 77 14 71 57 8 24 66 44 27 21 88 -9 39 73 47 58 39 59 89 6 72 79 86 25 34 69 37 26 75 73 42 42 8 44 47 70 70 35 -1 91 63 91 49 45 -2 22 69 21 15 35 31 53 21 84 77 69 10 22 60 55 57 40 78 76 55 56 23 76 11 -4 10 83 47 2 11 35 45 61 43 30 11 13 50 49 39 30 98 21 38 32 83 87 46 -6 63 45 21 56 22 95 38 45 77 81 97 35 72 99 3 7 57 75 71 64 40 56 20 44 89 -6 39 53 71 95 83 72 60 25 24 64 23 -6 94 12 62 91 56 70 94 52 68 65 2 26 78 28 50 23 2 51 81 93 59 72 93 -9 32 48 83 4 45 72 76 9 52 27 72 66 -6 1 95 30 -3 88 65 80 96 46 63 7 76 3 73 40 17 -1 70 5 66 77 66 27 49 43 53 -8 31 46 56 70 71 63 73 37 45 14 -7 22 23 -5 17 28 36 99 30 -5 34 78 71 55 -8 57 23 82 77 10 74 72 -2 88 76 50 23 -7 35 75 75 17 15 90 41 16 65 2 36 27 96 72 25 66 7 49 51 24 35 76 71 12 66 36 34 95 24 67 52 73 80 57 34 73 14 34 88 5 32 -1 -4 41 83 39 95 54 -5 76 73 51 20 34 91 11 48 68 93 38 3 1 95 85 -6 17 42 20 92 71 80 94 33 85 53 4 69 19 18 -4 83 41 93 80 98 99 85 3 55 10 8 -7 81 13 48 16 3 51 79 22 41 48 90 65 33 73 49 94 48 78 89 5 71 22 6 36 79 80 94 91 -2 3 96 90 27 57 10 9 10 47 19 39 40 27 46 68 32 54 77 -3 0 67 76 84 10 5 61 80 11 4 96 51 53 91 12 49 20 12 61 10 4 83 61 -5 90 62 47 7 25 59 87 96 29 48 79 18 87 29 3 33 35 72 97 64 13 72 23 8 72 51 53 2 73 79 56 20 -6 59 70 65 -6 29 85 18 70 77 39 68 23 90 8 75 33 38 73 49 63 11 49 66 27 4 47 84 66 45 6 61 99 33 53 27 56 62 8 40 15 44 44 91 39 97 20 52 73 98 1 61 42 8 19 19 10 40 8 -7 49 56 79 61 38 -8 -3 37 52 36 77 97 23 47 90 39 38 72 82 20 9 43 59 30 79 36 51 98 -8 41 55 6 88 0 48 55 64 65 63 96 14 27 64 69 36 18 -2 99 81 69 91 77 35 59 20 19 86 37 74 73 90 7 15 38 91 -1 57 32 74 96 78 45 30 17 -4 -6 27 10 16 1 -1 9 86 66 -7 81 -8 87 48 21 5 94 54 -8 0 58 76 49 7 -7 -1 70 6 47 40 99 72 56 87 -6 45 32 -6 50 19 70 7 16 43 60 87 -2 89 25 43 88 35 -6 54 93 4 12 83 39 41 36 1 57 98 -6 66 19 9 41 97 18 47 93 -8 9 92 18 90 1 97 21 70 68 15 82 84 14 86 41 81 75 20 33 3 75 11 28 10 16 62 33 69 97 70 52 15 79 49 72 20 66 29 52 69 58 58 40 90 85 63 38 73 -2 55 95 -7 -7 18 64 54 31 67 76 28 79 66 -6 54 21 58 -4 48 96 2 -4 0 65 9 97 40 21 22 12 13 15 76 17 29 28 7 3 9 46 31 14 58 58 35 84 27 35 -7 20 23 12 24 1 51 61 4 29 32 16 5 31 38 99 -7 30 22 57 40 52 34 35 1 10 70 30 57 55 13 24 93 58 0 26 89 49 65 65 23 75 98 28 97 72 24 18 93 25 -8 38 56 70 40 79 96 54 70 15 0 -6 68 98 63 8 50 77 93 40 85 49 86 69 1 77 98 49 80 70 92 96 27 -3 -6 24 52 72 57 36 68 16 45 60 32 53 80 16 -5 32 -7 67 86 30 87 70 90 49 39 33 29 75 41 36 14 95 -4 40 17 33 5 66 78 9 82 94 36 5 38 20 4 37 30 79 85 2 77 95 49 81 63 59 72 49 12 63 51 79 -2 54 99 80 57 47 -1 52 3 59 93 90 30 63 15 88 -8 5 96 66 50 23 -1 39 89 10 96 24 8 36 80 38 66 -5 85 10 94 87 -3 69 23 44 71 61 15 9 29 -9 12 63 27 37 23 -9 55 8 55 56 65 44 84 17 89 59 80 -9 15 49 33 66 99 91 67 51 81 41 84 45 60 -4 96 42 13 32 81 57 -1 39 41 10 4 18 7 27 -9 87 25 75 25 18 33 33 -3 95 97 10 46 93 1 23 28 48 52 -9 75 47 7 61 8 6 1 21 44 56 69 34 29 -8 28 84 72 85 90 48 23 30 18 46 60 23 81 5 5 9 37 61 66 12 94 78 19 -5 97 8 45 -4 82 97 41 77 58 73 -4 67 64 47 31 44 56 18 38 15 41 68 89 72 96 41 90 77 75 37 99 42 2 61 -2 51 67 -2 80 -2 22 84 21 49 97 42 97 31 59 37 38 46 31 11 74 2 70 7 11 96 52 23 81 39 46 9 7 57 60 89 86 25 58 78 12 20 57 67 87 65 42 20 -6 13 41 28 62 99 6 32 14 43 31 -3 93 60 35 75 89 15 5 35 99 47 49 95 35 32 3 70 46 34 87 55 85 22 52 50 53 24 65 95 58 91 83 17 25 64 20 98 70 26 20 32 53 96 12 86 78 23 1 4 23 84 97 22 66 99 71 39 3 88 28 -4 35 57 53 -4 49 14 90 43 59 49 11 77 37 -6 35 77 -6 27 47 -3 83 15 48 20 55 40 75 48 59 95 19 69 1 22 50 30 13 16 11 -4 84 34 99 61 41 51 24 -9 65 94 25 84 34 83 10 21 71 40 -3 13 25 78 49 57 31 45 99 93 81 1 96 78 43 87 92 21 74 38 70 75 88 30 53 48 71 97 4 79 23 31 90 31 66 56 95 5 25 -9 99 95 44 -3 60 -4 38 94 22 45 80 6 20 60 83 85 64 96 43 15 38 -7 77 -5 94 33 60 -7 40 96 22 51 25 93 -5 43 27 35 10 96 -3 39 51 1 98 35 87 13 78 52 38 -8 54 -2 44 4 52 93 64 22 17 26 18 24 2 75 86 64 -1 54 36 33 74 68 20 75 18 31 13 87 96 37 93 50 84 93 3 89 8 7 48 53 8 18 70 22 41 14 37 77 89 8 89 83 29 0 15 45 73 24 19 -2 12 50 88 92 43 82 67 87 83 17 21 23 -9 -6 0 36 -9 67 -9 15 38 83 69 25 49 98 56 35 51 73 50 -6 81 94 63 32 78 -4 37 13 79 72 46 -2 71 87 50 49 51 72 20 6 60 69 20 29 97 98 30 71 54 45 9 46 32 15 23 18 29 -4 38 51 96 16 68 70 24 98 18 14 -4 64 78 7 25 83 76 83 72 25 74 31 84 91 23 53 47 30 99 23 94 -3 63 42 -6 32 50 -4 57 -5 96 97 88 32 48 42 82 60 22 59 94 74 87 57 94 10 -3 40 45 23 6 86 64 23 53 73 61 86 83 1 61 -8 21 92 45 64 24 84 56 -9 95 71 33 32 37 59 20 13 82 88 52 53 -6 21 42 60 23 87 78 -1 46 24 6 94 13 37 96 81 24 32 92 53 77 36 43 43 -4 83 26 27 73 37 -3 73 65 20 80 41 90 89 28 15 12 19 31 5 5 19 39 15 52 44 -1 78 -2 39 82 62 98 81 72 7 77 98 58 0 65 5 94 -8 40 92 83 51 65 96 75 8 90 78 6 97 8 22 41 -2 22 -5 43 35 30 -2 25 47 62 49 72 -5 38 2 50 3 -7 4 4 98 61 94 75 14 53 52 6 5 46 20 88 35 26 2 86 -9 93 24 63 26 90 38 36 26 -2 17 60 57 78 47 34 -3 31 36 16 0 92 48 62 3 66 73 17 81 20 68 85 22 71 69 17 72 78 18 62 28 72 85 7 86 28 7 -5 99 54 91 18 9 -1 16 8 14 -4 3 28 76 62 43 42 62 3 12 36 -7 12 71 -1 30 60 -1 -2 11 14 38 21 18 59 90 96 53 8 8 78 97 14 46 -9 84 18 19 10 2 -8 -4 -8 -3 94 59 53 80 94 20 42 81 8 25 7 34 5 4 93 47 -2 -7 1 96 14 5 77 25 4 67 39 17 63 54 31 91 70 30 24 80 51 -6 31 32 58 44 68 48 63 14 7 83 92 14 21 -2 44 84 73 2 76 85 18 81 2 45 48 68 21 12 41 84 27 79 89 59 14 72 56 2 98 49 30 44 12 77 5 40 98 81 72 9 69 0 36 22 32 46 -1 20 94 18 99 69 40 -2 15 20 75 -7 20 27 23 36 88 -5 46 43 70 -9 10 80 77 18 4 83 94 -5 30 45 91 91 31 44 54 56 59 75 85 61 96 -6 17 18 27 29 4 33 63 99 26 30 38 53 22 4 74 62 42 20 52 59 48 49 74 11 83 5 68 -2 6 88 96 10 7 34 32 2 -5 64 2 52 82 85
Output
78 1074
Solution language
Solution
Stub generator input