Resource Allocation (dcmpe07)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: dcmpe07 */
/* TITLE: Resource Allocation (dcmpe07) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: OPTMODEL */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 7 from the Decomposition Algorithm */
/* chapter of Mathematical Programming. */
/* */
/***************************************************************/
data TaskData;
input profit weight start end;
datalines;
99 92 1 9
56 30 1 3
39 73 1 20
86 76 1 9
59 97 1 7
85 24 1 9
71 52 1 4
19 96 1 10
75 85 1 21
62 28 1 4
16 38 1 9
61 100 1 2
80 17 1 4
20 39 1 6
99 83 1 17
83 81 1 9
81 58 1 4
22 32 1 3
52 15 1 12
49 93 1 5
26 90 1 20
85 55 1 8
40 93 1 7
49 33 1 6
95 73 1 7
49 79 1 2
21 52 1 11
19 64 1 9
51 50 1 5
84 87 1 4
83 50 1 4
19 59 1 4
10 38 1 4
88 84 2 25
48 69 2 13
79 90 2 3
40 87 3 23
52 47 3 4
51 22 3 13
33 42 4 5
89 50 5 21
17 74 5 15
54 19 5 18
10 32 5 29
73 79 5 6
86 98 5 8
85 72 5 9
98 28 5 11
80 75 5 10
94 31 6 8
62 95 7 26
85 80 7 23
51 67 7 10
84 61 8 17
75 76 8 9
48 97 8 19
52 78 8 9
53 41 8 17
50 67 8 26
86 31 8 9
72 71 8 22
86 64 9 16
52 100 10 31
70 71 10 34
44 64 11 15
95 78 11 16
80 47 11 14
88 98 11 19
43 91 11 12
23 90 11 20
45 31 11 14
89 33 11 25
59 61 11 31
76 27 12 13
31 82 12 14
44 24 13 42
70 29 14 15
78 83 14 20
47 21 14 17
10 100 14 20
64 23 14 25
66 17 14 17
22 99 15 18
28 37 16 19
84 14 16 36
30 71 16 18
73 55 17 31
11 36 18 20
53 17 18 24
38 12 18 20
73 64 18 30
66 83 18 31
27 74 18 19
85 86 18 35
78 23 19 22
78 66 19 48
26 57 19 33
98 15 19 38
98 80 19 20
61 55 19 21
26 35 20 91
66 51 21 27
44 87 21 36
30 67 21 23
85 74 21 34
78 78 21 27
72 32 21 28
11 26 21 26
31 60 21 26
56 48 22 24
68 48 22 24
21 25 23 28
43 44 23 46
33 97 23 25
72 21 23 54
90 91 24 28
86 33 24 25
73 77 24 47
27 70 24 48
31 15 24 36
33 31 25 33
20 85 26 30
40 25 26 29
24 67 26 28
76 74 26 38
53 34 26 36
73 45 27 31
37 49 27 48
59 55 27 36
24 18 28 46
22 71 29 36
46 91 29 32
60 96 29 31
69 65 30 32
33 56 30 33
19 53 30 56
81 57 31 35
57 75 32 36
31 34 33 46
69 84 33 43
19 100 33 43
85 57 33 56
51 94 33 35
21 61 33 37
39 98 33 37
40 15 33 39
51 30 33 36
52 21 33 34
30 45 33 39
23 41 34 36
14 48 34 39
17 30 34 38
75 84 34 44
35 18 35 63
89 33 35 40
80 45 35 40
86 75 36 45
70 50 37 42
16 100 37 40
48 11 37 50
61 27 37 47
91 92 38 43
97 86 38 48
91 61 38 46
11 10 38 45
99 31 38 42
17 54 38 43
66 79 38 41
65 61 38 48
19 17 39 46
29 68 40 41
76 55 41 46
86 46 42 57
49 80 42 46
78 94 42 69
36 33 42 48
55 63 42 50
18 74 42 55
99 95 43 64
60 46 43 44
52 54 44 55
32 22 44 49
29 23 44 61
62 79 45 56
31 43 45 53
99 13 45 46
54 69 46 58
19 45 47 52
28 82 47 56
10 40 47 49
93 36 47 51
16 39 47 55
50 18 47 49
43 86 47 52
62 19 48 53
63 12 49 52
34 68 49 51
37 99 49 51
60 21 49 55
92 40 49 50
57 36 49 52
98 34 49 66
13 24 49 60
73 70 50 68
29 97 50 54
38 16 51 71
37 79 51 56
40 32 51 57
21 79 51 52
69 94 52 64
64 28 53 63
59 26 53 56
49 66 53 59
80 96 53 69
57 30 54 61
82 66 54 63
74 61 54 62
51 75 54 56
74 19 54 83
66 22 54 58
49 17 54 55
53 46 54 98
92 59 54 57
22 42 55 58
45 89 56 69
83 95 57 60
54 42 57 69
99 79 57 69
95 82 58 70
58 60 58 62
66 72 58 65
74 30 58 62
58 56 58 60
34 44 58 71
30 81 58 65
18 84 58 63
81 77 58 59
12 92 59 61
18 84 59 70
60 35 59 63
38 18 60 84
42 15 60 92
77 88 60 71
97 91 60 63
57 81 61 71
64 50 61 63
91 93 62 86
64 81 62 72
57 89 62 65
21 51 62 67
83 63 62 65
82 10 62 63
28 69 63 64
71 48 64 66
24 24 64 71
88 100 64 71
47 21 64 67
62 60 64 67
17 43 65 69
60 13 66 71
74 63 66 70
42 65 66 99
31 58 66 68
33 44 66 80
81 65 66 82
27 66 66 71
100 32 66 78
60 44 66 84
16 85 66 84
44 10 67 82
92 34 67 69
77 56 68 69
30 19 68 75
56 28 68 112
69 80 69 74
45 100 70 75
58 32 70 73
40 36 70 71
29 59 70 71
23 28 70 73
62 91 70 81
14 55 70 89
37 86 70 90
37 67 70 75
15 57 70 72
48 22 71 73
51 47 72 77
23 30 72 77
65 40 73 85
93 93 73 76
81 10 73 84
90 56 73 75
22 27 73 78
56 96 73 74
35 100 73 105
62 78 73 86
53 28 74 113
32 28 74 76
82 52 74 79
49 83 74 76
100 35 75 79
26 28 76 77
83 70 76 90
18 81 76 77
88 52 77 87
34 72 78 87
95 63 78 81
33 91 78 79
11 94 78 92
85 29 79 82
44 49 79 92
38 81 79 85
26 32 79 89
68 96 79 80
59 69 80 88
53 27 80 94
78 89 81 83
53 24 82 94
67 67 82 92
97 18 82 84
37 25 82 85
18 10 83 84
92 22 84 93
57 59 85 102
91 54 85 87
80 22 85 86
64 50 85 96
58 35 86 98
84 96 86 114
52 41 86 99
10 19 86 88
34 55 86 93
90 27 86 91
24 21 87 109
61 25 87 89
56 18 87 97
62 67 87 88
11 66 88 91
79 42 88 92
22 23 88 89
73 99 88 97
91 92 89 101
34 10 89 95
40 52 89 90
54 59 90 108
23 17 90 113
90 89 90 91
94 46 90 96
92 68 90 94
61 45 91 96
69 33 92 94
51 48 93 101
61 21 93 106
33 31 93 94
88 53 93 97
90 65 93 104
66 84 93 117
99 14 93 101
17 22 93 99
30 92 93 96
79 45 93 95
33 24 94 96
17 26 95 115
72 100 95 103
69 75 96 115
23 51 97 104
18 18 97 117
100 50 97 104
52 34 97 134
11 25 97 98
77 83 97 112
61 26 98 104
23 57 98 110
26 25 98 103
80 49 99 110
99 39 99 100
58 32 99 102
76 10 99 101
80 50 99 100
26 59 100 101
27 17 100 105
59 41 100 106
51 49 100 103
57 25 100 110
58 90 101 104
86 81 102 104
21 95 102 118
50 31 102 104
92 14 102 105
83 26 102 107
63 57 103 117
74 70 103 115
64 17 103 115
84 12 103 110
47 48 104 128
15 74 105 115
76 80 106 124
85 99 106 109
39 94 106 108
67 68 106 130
57 94 106 122
51 65 106 108
19 75 106 120
10 50 106 107
14 50 106 109
56 56 106 109
89 26 107 112
57 22 108 111
54 11 108 127
81 98 108 111
60 14 109 115
68 30 110 111
15 15 111 116
22 79 111 117
84 65 111 113
31 41 111 112
37 94 111 120
10 79 111 116
97 33 111 125
89 77 112 119
62 34 113 123
19 45 113 115
17 78 113 119
93 48 113 115
50 60 113 115
46 99 113 114
34 65 113 121
18 17 113 124
96 55 114 117
15 36 114 119
16 84 114 122
49 83 114 115
10 34 115 131
73 26 116 119
38 93 116 122
10 34 116 123
100 12 116 118
67 77 116 126
36 58 116 129
74 15 116 117
51 48 116 117
63 27 116 118
70 60 116 124
96 77 116 117
43 83 116 134
21 41 117 119
70 19 118 127
60 91 118 122
17 86 118 120
19 43 118 133
84 42 118 121
67 59 118 126
13 73 118 125
58 42 118 121
55 28 119 120
91 20 120 124
48 53 121 122
42 32 121 151
21 75 121 131
23 65 121 125
84 17 121 139
50 18 121 126
35 34 121 124
45 75 121 139
10 69 122 131
96 100 123 124
71 43 123 138
22 36 123 139
71 32 123 133
42 60 123 133
100 81 123 129
74 88 123 124
74 97 123 130
32 94 123 124
51 91 124 141
63 66 125 144
76 44 125 133
30 84 125 144
97 36 125 128
70 77 126 139
89 28 126 139
36 91 126 129
23 13 126 137
22 39 126 132
19 33 126 129
95 80 127 133
61 37 128 130
69 80 128 129
69 42 128 136
88 26 128 132
48 49 128 132
79 77 128 136
99 47 129 138
92 23 130 131
87 55 130 135
55 56 130 137
74 95 130 153
42 37 130 139
76 82 131 140
76 87 132 135
70 29 132 135
49 77 132 138
97 36 132 133
60 58 132 150
35 43 133 142
22 36 134 141
36 78 134 136
18 31 134 141
69 87 134 141
37 97 134 145
52 45 134 138
40 84 134 176
99 65 134 139
84 57 134 135
31 23 134 137
13 41 134 145
35 24 135 146
17 38 136 145
36 39 136 139
32 33 136 140
43 89 136 147
35 87 136 141
52 69 137 212
46 83 137 140
22 78 137 143
23 26 137 155
61 78 138 144
79 99 139 146
35 53 140 142
47 36 140 147
74 16 140 148
52 46 140 142
78 10 140 150
62 86 140 147
100 43 140 143
23 28 140 150
38 21 140 146
61 58 140 141
64 99 141 147
89 27 142 149
93 31 143 162
98 40 143 147
30 80 144 157
77 31 144 147
56 75 144 147
20 53 144 156
49 55 144 148
77 16 144 158
37 39 144 155
76 78 144 145
60 64 144 158
73 73 144 152
60 60 144 149
80 49 144 157
65 23 144 147
79 47 145 155
87 99 146 152
11 87 146 148
54 63 146 155
36 22 146 154
83 95 146 147
34 28 146 147
16 94 147 156
88 50 148 149
49 75 148 152
67 67 148 154
92 41 149 177
66 62 149 153
96 83 149 155
72 89 149 162
76 51 149 167
60 89 149 162
13 75 149 151
12 76 149 151
99 77 149 168
86 79 149 165
61 12 149 151
42 85 149 153
43 94 150 153
90 14 150 161
77 13 151 182
67 69 151 158
31 47 151 167
97 87 151 156
52 88 152 162
65 32 152 166
41 85 152 166
30 100 153 162
83 44 154 155
20 89 154 175
46 25 155 190
13 15 156 160
44 96 156 162
22 23 156 168
36 40 156 164
38 50 156 160
46 48 156 166
38 91 156 159
77 68 156 164
96 74 156 172
49 100 157 180
85 44 157 159
29 19 157 172
68 75 157 160
75 39 158 159
42 81 158 161
74 71 158 162
76 46 159 166
33 20 160 161
80 10 161 163
22 31 161 187
90 70 161 163
41 31 161 166
58 86 161 165
27 27 161 162
22 78 162 163
27 57 163 171
22 45 163 164
19 51 163 169
36 98 163 182
69 93 163 164
43 11 164 177
26 82 165 169
97 55 165 181
35 10 165 178
50 52 165 187
62 11 165 166
49 85 165 170
30 23 165 169
45 27 165 172
40 49 165 166
25 63 165 181
74 31 165 168
40 48 165 175
31 57 166 167
62 19 167 174
75 13 167 196
76 35 167 174
40 98 167 177
33 20 167 168
83 54 167 171
69 98 168 185
45 27 169 186
37 42 169 195
74 96 169 173
30 95 169 170
44 21 170 181
19 41 170 185
98 18 170 173
59 19 170 206
19 95 171 172
52 79 172 177
17 72 173 174
45 82 174 179
82 92 174 178
28 57 174 181
52 77 174 176
31 33 174 176
56 86 174 176
75 14 174 185
74 95 174 184
61 43 174 177
59 26 174 177
27 22 175 177
20 30 175 179
32 28 176 183
38 69 176 180
12 67 176 178
47 24 177 191
74 88 178 182
68 76 179 190
66 91 179 186
35 91 180 195
37 22 180 198
34 78 180 182
66 74 180 187
42 50 180 183
49 79 180 193
63 67 180 188
98 63 180 182
82 19 180 187
25 69 180 202
90 12 180 183
47 85 181 186
70 85 181 182
20 17 181 218
22 81 181 204
73 98 182 189
32 68 183 184
11 79 183 198
41 59 183 192
72 57 183 190
38 11 183 188
80 99 183 184
35 17 183 190
29 35 183 187
73 47 184 202
19 83 184 196
90 44 185 200
35 72 185 188
74 56 186 189
30 39 186 187
68 59 186 187
80 73 186 191
85 77 186 197
92 56 187 193
50 73 188 216
39 97 188 196
17 64 188 198
13 97 188 194
86 17 189 190
81 47 189 213
93 29 189 190
27 18 189 191
77 60 189 214
58 69 189 196
100 34 189 197
23 63 189 202
98 80 190 192
48 11 191 193
71 49 191 199
84 18 191 196
56 26 191 199
92 74 191 199
79 41 191 200
69 89 191 193
55 57 191 198
14 13 192 196
65 53 192 194
94 48 193 196
29 48 193 202
17 74 194 196
17 44 194 205
18 37 194 196
21 55 194 200
73 41 195 197
74 81 196 214
81 53 197 198
16 93 197 205
10 74 197 249
56 70 197 202
70 23 197 200
95 76 197 206
52 79 197 204
48 89 197 207
97 81 197 209
20 43 197 201
40 72 197 207
83 32 197 224
47 89 198 224
37 17 199 201
55 46 199 211
96 55 199 202
17 63 199 206
50 36 199 213
77 21 199 215
74 14 199 211
13 65 200 206
96 87 200 203
84 38 200 203
98 98 200 201
26 48 201 208
78 80 201 209
82 24 202 204
28 78 203 233
92 46 203 222
12 18 204 213
43 99 204 209
89 51 204 227
30 13 204 206
66 15 205 212
27 44 205 206
32 64 205 210
20 24 205 211
77 87 205 206
16 71 206 217
52 76 207 219
70 90 207 208
46 35 207 224
36 49 207 208
74 79 207 227
57 87 207 209
97 31 207 210
91 27 207 222
22 70 208 210
100 49 208 262
52 96 208 211
86 30 209 223
88 33 209 214
60 13 210 215
70 53 210 217
64 23 210 236
97 47 210 217
100 90 210 219
86 16 210 212
93 52 211 213
79 71 211 218
54 50 211 241
29 64 211 219
96 48 212 213
64 44 212 213
50 64 213 226
49 21 214 216
39 52 214 215
84 54 214 227
28 66 214 216
29 88 214 217
74 19 215 221
21 38 215 217
68 53 215 222
13 24 215 217
10 32 215 226
42 89 216 246
39 10 216 222
89 49 216 218
67 32 216 220
50 31 216 227
85 81 216 222
13 88 217 235
68 48 218 220
72 94 219 244
22 82 219 225
44 60 220 222
33 40 220 225
72 40 220 231
73 11 220 225
10 30 220 225
25 20 220 223
43 29 220 222
71 22 220 225
57 41 220 229
38 66 220 221
10 26 221 225
83 39 222 231
17 88 223 241
95 46 223 257
11 53 223 235
75 34 223 225
36 22 223 225
32 91 223 231
69 44 223 233
24 98 223 224
33 82 223 225
14 66 224 227
41 79 224 237
64 22 224 225
91 19 224 227
72 73 225 226
94 11 226 231
89 87 226 231
60 85 226 228
75 18 226 228
92 29 226 242
55 54 226 238
22 55 226 232
96 94 226 237
38 56 226 240
50 17 226 230
56 13 226 233
87 64 226 230
75 62 227 242
29 28 228 230
10 72 228 229
60 70 228 236
26 38 228 249
43 33 229 232
75 16 229 242
68 54 229 243
52 59 229 237
36 83 229 230
73 94 230 232
81 100 231 235
22 33 232 234
45 44 232 234
62 16 233 235
86 10 233 244
39 39 233 237
18 94 233 234
100 52 233 237
18 31 233 241
81 56 233 237
53 87 233 235
36 85 233 234
64 86 233 248
26 20 234 235
39 10 234 239
80 70 234 244
66 85 235 236
97 38 236 237
78 27 236 265
75 47 236 239
57 39 236 237
38 78 236 245
89 32 236 238
48 95 236 245
66 41 236 240
33 55 236 237
62 86 237 242
92 73 238 247
81 49 238 242
79 86 238 242
91 92 238 255
58 56 238 239
44 57 238 240
84 75 239 246
73 12 240 242
45 82 240 242
87 92 240 242
99 84 240 247
57 24 240 250
97 86 241 244
84 18 241 243
25 31 241 244
70 93 241 263
77 54 241 242
72 11 241 247
27 91 241 244
54 95 241 257
30 40 242 247
34 22 243 253
82 57 243 254
70 72 243 252
23 25 243 244
79 74 243 258
89 88 243 248
34 10 243 246
76 44 243 252
64 76 244 248
56 26 245 249
71 13 245 253
99 49 245 252
99 59 245 256
68 51 245 260
17 40 245 257
55 37 246 259
89 33 246 258
64 28 246 247
32 17 246 259
15 75 246 249
72 70 246 247
91 37 246 277
73 49 247 250
80 67 248 251
15 13 248 250
28 82 248 252
96 43 248 258
27 83 248 261
71 16 248 261
58 45 248 254
78 94 249 251
33 90 250 265
93 64 250 251
96 54 250 254
51 65 251 254
23 11 251 253
18 31 251 255
22 92 251 255
43 34 251 254
79 40 251 252
58 75 251 252
89 16 251 274
94 26 252 263
33 31 253 258
80 34 253 259
64 55 253 265
76 72 253 256
61 63 254 261
54 30 255 268
84 49 256 262
45 83 256 292
90 79 256 260
85 90 256 264
85 73 256 270
49 60 256 258
36 26 256 268
67 13 256 265
20 92 256 261
51 39 256 266
29 51 257 269
89 65 258 265
83 86 259 284
78 86 259 276
90 57 259 262
68 39 259 264
62 10 259 262
56 36 259 261
16 89 259 272
95 46 259 261
62 100 259 267
90 63 259 269
47 31 259 260
33 35 260 267
75 67 260 265
54 56 261 277
31 83 262 267
63 17 263 266
42 92 263 269
60 77 263 297
71 82 263 266
15 43 263 267
61 89 263 274
45 34 263 299
53 72 263 289
81 86 264 265
33 32 264 274
44 17 264 267
48 79 265 268
66 19 266 271
86 96 266 269
49 10 266 273
100 51 266 267
100 91 266 269
71 34 266 267
46 36 266 271
87 72 266 276
53 21 266 274
74 58 266 273
10 87 266 269
35 59 267 302
93 65 268 290
96 28 268 275
55 85 268 279
70 40 268 269
16 36 268 270
10 60 269 286
81 28 270 274
37 10 270 272
13 48 270 284
56 90 271 279
50 33 271 281
65 20 271 280
76 67 271 277
99 17 271 273
57 74 272 278
98 37 272 274
20 26 272 282
89 96 272 282
40 86 272 275
11 69 272 286
20 24 273 278
74 62 273 276
35 67 274 286
20 54 275 279
47 43 275 283
78 86 275 282
41 91 275 277
29 81 276 277
39 14 276 282
65 68 276 278
32 59 276 288
27 95 276 295
57 36 276 282
80 70 276 280
21 60 276 277
40 92 277 281
74 87 278 288
90 38 279 286
99 43 279 282
83 82 279 283
61 81 279 285
74 57 279 280
13 85 280 286
40 89 280 286
57 98 280 296
26 79 280 289
96 47 280 283
91 61 280 286
40 28 281 285
48 96 281 291
28 54 281 288
90 38 282 338
97 19 283 285
78 42 283 288
23 49 283 286
87 45 284 285
71 68 284 287
82 53 284 297
49 60 284 293
81 98 284 286
30 23 284 290
52 100 284 287
55 62 284 298
35 79 284 290
21 99 285 292
85 50 285 301
41 60 285 286
32 48 286 288
37 84 287 299
64 57 287 299
41 36 287 296
12 87 287 288
82 64 287 296
73 81 287 289
21 22 287 293
81 58 287 320
45 47 287 290
44 38 287 291
12 56 288 292
77 27 289 311
86 45 289 294
47 33 289 293
58 77 289 290
23 100 290 296
44 12 291 296
28 93 291 294
40 58 291 295
58 10 291 296
41 18 291 313
39 48 291 301
50 86 291 299
58 62 291 311
32 21 292 296
28 17 292 303
100 13 292 310
88 95 292 293
53 22 292 296
76 61 292 293
15 60 292 316
52 18 293 298
96 28 294 299
38 84 294 308
20 26 294 301
63 15 294 296
15 32 295 297
98 78 295 304
48 15 295 296
71 41 296 299
41 83 297 299
63 58 297 318
11 36 297 300
71 13 298 328
38 35 298 301
62 95 298 300
40 43 298 310
50 17 298 302
31 87 298 322
17 79 298 306
19 31 298 305
72 26 298 311
89 28 298 311
17 65 298 301
16 47 299 301
25 21 300 322
48 23 300 322
28 52 300 308
16 37 300 301
38 26 300 302
95 21 300 301
15 22 301 307
13 24 302 303
75 38 302 306
63 87 302 306
99 75 302 328
75 29 303 308
80 26 303 314
10 44 303 304
34 68 303 309
84 15 304 317
21 63 304 307
50 27 304 305
13 83 305 307
27 81 305 315
26 10 305 306
22 28 305 307
57 25 305 314
20 90 305 315
92 78 306 313
63 44 306 307
68 64 307 309
76 71 308 312
76 80 308 343
84 43 308 319
65 28 308 322
27 20 308 318
79 76 308 328
70 14 309 314
49 83 309 312
88 58 310 313
14 46 310 318
10 44 310 316
51 32 310 328
94 19 310 313
92 42 311 319
23 81 312 313
90 81 312 313
31 58 312 328
95 20 312 318
21 34 312 318
31 51 312 319
13 13 313 315
86 71 314 322
66 49 315 318
94 86 315 332
75 44 315 319
74 81 316 317
93 72 316 322
84 93 316 317
84 32 316 330
24 60 317 320
51 75 317 321
98 85 317 322
54 100 317 331
93 66 317 352
74 17 317 322
59 29 317 330
45 63 317 318
21 87 317 318
17 86 318 341
29 71 319 321
76 80 320 328
51 53 320 336
37 51 321 326
69 92 321 325
61 18 321 322
20 68 321 324
87 13 321 324
30 67 321 323
11 52 321 329
51 81 321 323
90 44 321 323
45 32 321 329
81 68 321 334
78 91 321 345
10 52 322 333
37 21 323 354
13 28 324 328
67 33 324 325
22 30 324 341
31 35 324 341
22 92 325 326
39 61 325 327
92 80 325 338
32 25 325 338
70 62 325 330
71 53 325 331
20 84 326 334
65 82 326 327
69 57 326 328
22 81 327 328
70 59 327 347
49 61 327 335
98 49 328 330
95 24 329 338
40 74 329 337
21 38 329 333
81 95 329 341
98 49 329 340
55 49 329 330
93 83 329 338
44 26 330 341
77 84 331 332
89 34 331 341
58 17 331 349
88 62 332 355
87 63 332 335
57 47 333 336
33 41 333 338
31 51 333 334
31 37 334 335
37 26 334 339
40 47 334 336
92 72 334 341
30 41 334 337
82 52 335 339
53 20 335 340
49 52 335 348
42 27 335 338
45 90 335 339
51 99 335 352
59 59 336 359
80 82 336 346
50 90 336 338
53 20 337 344
79 69 337 346
89 32 337 338
59 72 337 341
75 51 338 344
26 24 339 356
60 97 340 343
32 95 340 347
42 93 340 346
49 84 340 361
37 24 340 342
69 36 340 345
26 20 340 342
99 55 340 349
98 12 340 351
30 13 340 341
12 10 340 352
72 41 341 342
18 76 342 345
90 98 342 346
75 37 342 348
77 39 343 367
74 16 344 348
42 88 344 352
10 37 345 347
25 90 345 363
59 58 345 366
20 95 345 380
66 84 345 355
90 56 345 346
78 36 345 380
39 17 345 356
32 11 345 352
47 55 345 348
63 69 345 348
49 84 345 353
96 44 345 362
75 62 346 348
63 79 347 351
17 59 347 359
51 57 347 350
62 65 348 400
42 63 349 350
59 95 349 354
13 49 350 352
14 21 350 358
92 67 350 351
30 45 350 353
75 67 351 366
73 17 351 358
50 36 351 356
55 28 351 352
22 21 351 352
62 53 351 353
71 28 351 363
49 76 352 357
85 29 353 355
12 24 353 358
41 55 353 360
91 45 353 360
86 57 353 358
56 15 353 355
23 56 353 379
57 94 353 359
22 67 353 366
34 43 353 370
68 25 354 365
65 54 354 363
48 38 354 366
11 91 354 366
24 100 355 366
97 36 355 358
58 31 355 392
100 85 356 364
46 98 356 357
34 67 356 377
75 98 357 359
78 27 357 373
74 72 358 361
37 54 359 361
60 88 360 361
46 90 360 387
74 92 360 372
64 37 360 378
26 88 360 375
19 88 360 364
99 92 361 362
26 28 362 390
29 61 363 364
40 44 363 365
48 82 363 407
21 58 363 370
67 98 363 378
31 82 363 366
77 97 363 368
94 45 363 364
21 68 363 366
45 47 363 382
34 68 364 369
63 38 365 366
94 22 365 366
97 78 365 367
16 10 365 366
99 93 365 372
70 65 365 368
18 64 365 371
79 20 366 379
24 89 367 371
87 94 367 370
86 46 367 375
23 58 367 375
76 19 368 373
59 40 368 369
19 95 368 379
38 48 368 373
75 59 368 379
47 71 368 369
16 24 369 377
67 70 369 374
51 23 370 404
17 88 370 393
46 75 371 374
97 31 371 381
49 95 371 372
80 52 371 384
67 65 371 373
59 76 372 374
54 51 372 373
48 64 372 377
28 78 372 378
94 86 373 381
83 54 374 387
97 19 375 378
23 94 375 384
22 36 375 382
18 61 375 376
100 24 375 376
99 18 375 389
93 86 375 387
96 27 375 387
20 40 375 387
100 47 376 382
18 50 376 397
37 42 377 389
85 57 377 379
21 46 377 386
61 61 378 380
47 62 379 382
65 60 380 382
34 23 380 388
43 66 380 385
46 51 380 385
88 75 380 384
51 50 380 385
59 72 381 385
27 18 381 391
87 89 381 387
63 18 381 382
31 43 381 383
44 14 381 402
20 27 381 383
11 68 381 396
96 66 382 385
79 74 383 415
24 30 383 392
54 16 383 386
41 96 384 418
36 22 384 388
63 66 384 394
98 67 384 386
20 98 384 421
97 89 384 417
24 43 384 385
29 12 385 388
64 78 386 391
29 20 386 393
73 13 386 387
71 58 386 395
10 28 387 399
20 81 388 403
41 71 388 392
51 49 388 391
28 42 388 393
96 29 388 394
52 67 388 390
77 85 389 392
43 98 389 392
13 54 389 406
51 47 389 392
88 90 389 402
92 16 389 390
58 26 389 415
46 81 390 396
94 36 390 403
83 79 391 405
18 34 391 392
33 64 391 410
77 98 391 395
57 46 392 397
74 63 393 398
72 49 393 399
40 36 393 396
94 49 393 401
77 44 393 406
61 92 393 394
11 83 393 401
48 93 393 394
40 38 394 433
27 51 394 413
15 53 394 395
93 22 394 400
43 69 395 420
37 11 395 398
47 76 395 396
17 96 395 399
26 40 396 408
16 30 396 397
52 88 396 401
92 98 396 407
51 48 396 398
43 15 397 423
33 86 398 403
48 30 399 407
95 73 399 414
42 23 399 409
39 97 400 410
92 36 401 402
26 73 401 406
92 32 401 407
67 26 401 413
68 16 401 403
34 85 401 407
51 31 401 403
37 44 402 406
64 95 402 404
90 42 403 408
15 28 404 414
39 59 404 406
51 19 404 412
87 99 404 405
47 46 404 410
55 56 405 410
71 38 405 406
74 59 405 409
96 77 405 411
90 80 405 406
74 95 405 437
18 69 406 413
89 17 407 432
15 99 408 419
59 55 408 409
96 44 408 416
16 100 408 409
51 65 408 413
58 18 408 410
75 71 408 420
27 85 408 417
52 71 408 411
58 82 408 415
63 51 408 412
72 32 408 412
94 53 409 413
57 21 409 413
10 85 410 416
95 59 411 425
31 16 411 419
64 40 411 420
96 99 411 423
23 37 412 417
92 92 412 418
68 79 412 417
60 99 412 416
63 49 413 417
38 89 414 415
79 51 414 432
72 97 414 417
24 86 414 417
71 37 414 419
14 56 414 415
72 39 414 421
18 78 415 423
69 36 416 424
72 32 416 422
20 94 416 426
34 37 416 435
32 80 416 427
34 100 416 417
80 16 416 426
91 41 416 419
54 88 416 417
19 30 416 417
91 98 417 431
28 76 418 425
43 64 418 424
23 11 418 423
10 61 418 433
39 10 418 430
44 55 418 433
34 49 418 428
32 10 418 419
69 36 418 422
47 70 419 436
88 22 420 423
68 43 421 427
77 17 421 424
74 69 421 427
48 48 421 429
77 49 421 427
55 53 422 439
48 98 422 427
100 13 422 427
98 19 422 423
72 91 422 437
62 95 422 432
79 29 423 427
36 45 424 444
67 92 424 425
45 32 424 426
51 41 424 428
23 72 425 429
88 38 425 441
86 61 425 427
10 50 425 428
58 68 425 426
23 78 425 442
73 24 425 430
34 96 425 430
22 94 426 438
76 31 427 439
92 95 428 440
10 24 428 432
50 65 428 430
16 22 428 432
66 47 428 430
97 56 428 429
16 13 428 431
25 94 428 446
17 17 428 432
32 13 428 436
39 35 428 435
53 70 428 429
20 47 428 434
54 80 429 430
12 16 430 448
90 15 431 449
13 29 431 461
20 19 431 434
22 38 431 440
79 14 431 437
73 56 431 440
97 53 431 437
84 68 432 434
16 34 433 438
75 11 433 444
76 21 433 439
19 14 433 434
22 51 434 442
86 98 435 436
85 46 435 439
54 10 435 440
32 73 435 454
23 64 435 437
30 30 435 436
19 50 435 438
13 10 435 447
51 94 436 441
94 46 436 437
87 91 436 437
93 69 436 443
54 49 436 439
54 15 436 444
23 13 436 444
93 57 437 440
38 53 438 451
50 27 438 444
80 23 438 458
90 75 438 443
45 35 438 447
18 84 438 439
18 21 438 449
39 70 438 442
93 54 438 444
82 69 439 446
100 78 440 443
68 84 441 445
39 50 441 470
61 29 441 442
14 64 441 450
94 84 441 454
45 76 441 444
80 63 441 451
20 60 441 449
26 100 441 449
42 70 441 451
38 62 441 458
57 88 441 449
39 12 442 451
56 98 442 445
64 100 442 449
13 11 443 457
26 71 443 463
45 80 443 457
59 54 444 447
63 21 445 451
40 25 445 446
92 80 446 452
65 60 446 449
35 38 446 468
78 65 446 453
84 39 446 449
19 30 446 449
77 35 446 451
95 10 446 464
87 71 446 451
75 32 446 459
47 14 447 448
78 53 448 450
14 18 448 456
94 61 448 449
96 66 448 449
99 98 449 452
22 100 450 466
97 97 450 455
10 80 450 459
58 80 450 455
81 32 450 463
74 93 450 453
53 42 450 453
53 20 450 470
65 23 450 451
79 66 450 456
61 30 450 452
99 72 451 456
95 51 452 456
80 99 452 477
33 15 452 481
53 61 453 481
66 17 454 457
10 23 454 461
61 56 454 456
65 21 454 465
64 63 455 461
65 15 455 459
64 27 455 456
32 100 455 456
17 90 455 469
71 59 455 468
42 50 455 456
63 99 455 514
14 18 455 456
36 98 456 468
26 80 457 479
13 91 457 463
97 68 457 460
33 71 457 472
29 41 458 488
50 61 458 466
73 75 458 497
72 25 458 462
40 42 459 461
19 54 459 460
66 19 460 467
53 69 460 473
61 63 460 465
61 34 460 464
49 66 460 461
76 44 460 461
66 26 460 461
95 92 460 462
26 12 460 461
51 38 461 464
65 65 462 475
72 16 462 484
12 34 462 476
93 20 462 475
23 39 462 468
90 81 462 491
71 91 462 466
55 86 463 472
68 97 464 465
32 85 464 479
61 72 464 469
90 32 464 466
54 36 465 469
77 82 465 467
54 38 465 471
56 25 465 467
67 51 465 487
25 93 465 470
48 28 466 470
73 17 466 470
65 33 467 470
93 32 468 484
20 70 469 471
56 41 469 480
97 10 469 482
11 12 469 470
19 51 469 475
65 73 469 472
18 20 469 521
35 30 470 480
47 33 471 476
89 49 471 473
50 69 472 474
18 80 472 495
40 58 472 475
61 44 472 478
86 27 472 474
63 54 472 473
22 32 472 479
28 62 473 486
37 55 473 505
87 54 473 479
12 17 473 478
25 28 474 483
23 86 474 476
71 78 474 480
62 73 474 482
78 79 474 477
47 96 475 478
79 57 476 477
29 89 476 479
28 60 476 484
93 71 476 479
57 48 476 479
96 59 476 482
84 23 476 481
75 44 477 484
62 42 477 488
39 28 478 479
99 54 478 484
42 16 478 482
27 60 478 483
12 72 479 487
21 88 480 487
21 57 480 484
91 11 480 490
86 69 480 488
73 59 480 484
30 32 481 484
83 18 481 485
41 82 481 496
70 99 481 500
55 11 482 483
59 74 483 513
53 50 483 491
61 70 483 484
85 79 483 492
58 82 483 485
97 50 483 495
79 76 483 485
59 79 483 492
36 79 484 510
31 97 485 490
52 47 485 511
65 93 485 489
66 12 485 486
96 44 485 520
35 37 485 491
96 82 485 493
39 14 485 503
32 95 485 505
10 82 485 493
83 73 485 489
48 12 485 503
87 82 486 488
19 82 486 494
71 32 487 490
37 38 488 496
81 81 488 489
96 57 488 494
95 84 488 489
43 73 488 506
15 18 489 491
65 53 489 494
19 54 489 491
60 98 489 494
43 99 490 498
51 56 491 498
100 48 492 493
93 94 492 501
46 49 492 505
60 54 492 493
91 94 492 502
17 49 492 495
86 66 492 519
96 46 492 504
46 49 493 499
77 25 494 496
83 84 495 499
77 18 495 497
73 15 495 502
40 55 496 499
25 18 497 504
42 47 497 508
12 45 497 501
53 70 497 500
70 45 497 504
78 70 497 501
99 82 497 517
43 36 497 502
44 21 497 515
58 19 497 498
44 51 498 507
82 51 499 503
10 93 499 501
18 29 499 500
26 88 499 505
96 88 499 505
91 97 499 520
32 54 500 507
20 50 500 522
58 41 500 513
74 21 501 502
85 37 501 515
69 34 501 507
21 100 501 503
41 26 501 505
99 55 502 508
67 81 502 520
64 97 502 511
42 77 502 507
26 13 503 518
90 32 503 516
81 56 503 513
39 71 504 506
28 22 504 511
57 64 504 505
10 63 505 509
24 30 506 510
91 72 506 509
25 10 506 512
44 40 506 507
97 94 506 510
94 10 506 511
14 71 506 524
78 46 506 507
10 98 507 514
93 83 508 509
79 13 508 511
87 12 509 519
41 54 509 510
38 62 509 510
86 36 509 520
97 21 509 517
61 45 509 511
65 54 509 526
87 86 509 516
68 14 510 512
88 76 511 517
16 45 512 519
93 47 512 518
89 57 512 531
35 75 512 545
51 31 512 515
69 25 512 514
93 52 513 517
17 99 514 528
12 70 514 523
87 85 514 531
73 93 514 515
18 87 514 528
52 42 514 522
36 90 514 517
46 34 514 524
78 36 514 515
56 37 515 527
59 78 516 529
95 62 516 518
82 97 516 533
15 35 517 524
87 14 518 522
40 96 518 525
95 92 518 521
99 48 518 520
62 29 518 530
94 38 518 530
82 97 518 524
71 47 518 534
38 67 519 523
68 25 519 528
81 52 519 524
57 95 520 534
73 75 521 530
21 87 522 536
46 44 522 527
42 27 522 532
87 93 522 524
75 99 522 525
64 30 523 526
26 13 523 532
42 49 523 529
29 73 523 525
39 19 524 532
43 92 525 532
27 56 525 543
60 54 525 536
17 51 525 551
69 65 525 530
44 35 525 536
95 12 525 527
22 65 525 530
40 26 526 547
52 75 526 528
82 28 527 551
10 33 527 529
76 100 528 537
86 88 529 540
92 90 529 559
23 43 529 535
13 46 529 543
33 48 529 552
56 95 529 535
37 71 529 541
77 11 529 530
64 21 529 534
12 10 529 534
47 67 529 532
92 19 529 530
65 44 530 533
50 68 531 536
33 58 531 539
16 100 532 533
81 92 533 537
23 96 533 538
51 73 533 543
51 71 533 538
21 66 533 534
16 66 533 539
24 74 533 545
80 91 533 537
96 75 533 536
42 99 533 534
83 70 533 555
66 75 534 549
64 24 535 543
21 51 535 552
73 80 535 543
89 13 535 544
23 63 535 538
67 22 535 540
51 48 535 536
62 82 535 543
65 45 536 545
24 95 537 542
76 61 537 539
23 47 537 544
13 22 538 550
29 31 538 539
23 18 538 540
10 38 539 543
87 59 540 580
26 21 540 541
28 19 540 554
21 44 540 543
52 73 540 546
23 82 541 546
55 30 541 549
67 95 541 543
93 38 541 542
90 41 541 542
32 29 542 556
38 92 542 547
89 47 542 548
95 45 542 549
63 65 542 573
91 32 542 559
35 34 542 545
58 33 543 546
50 80 544 551
89 50 544 547
20 87 544 551
88 90 544 553
38 92 544 545
22 87 545 557
45 39 546 550
83 71 546 561
42 30 546 559
13 99 546 547
62 27 546 548
35 47 546 572
44 41 546 564
46 34 546 548
75 39 547 561
17 87 548 556
75 31 548 551
69 93 548 581
14 38 548 550
92 42 548 550
99 53 549 554
87 23 549 555
69 53 549 571
48 18 549 567
66 24 549 559
56 47 549 550
68 91 549 551
29 44 550 553
26 44 551 559
97 25 552 564
55 10 552 558
27 21 552 581
44 48 552 555
23 96 553 562
23 17 553 561
12 48 554 559
72 44 554 556
71 94 554 564
67 29 554 555
67 91 554 560
38 98 554 560
94 57 554 563
74 70 554 556
97 66 554 570
86 32 555 570
15 29 555 558
23 80 555 563
38 56 556 576
22 22 556 557
27 69 557 568
89 26 557 564
100 71 557 575
86 21 557 558
85 63 557 559
41 22 558 562
64 60 559 566
60 73 560 573
90 48 560 561
80 71 560 564
95 100 560 576
49 66 561 568
75 76 562 564
45 33 562 576
29 72 562 582
88 84 562 564
100 49 562 567
82 86 562 578
92 78 562 564
27 59 562 574
95 47 563 565
33 19 563 567
72 10 563 569
14 90 563 565
21 89 563 564
99 27 563 567
86 25 564 579
38 53 565 566
96 49 565 569
26 68 565 580
96 72 565 569
70 95 566 571
96 29 566 571
72 76 566 572
10 80 566 567
71 82 566 576
65 48 566 580
99 27 566 580
63 34 567 568
40 21 568 577
80 65 569 571
78 13 570 571
67 36 570 576
16 100 570 573
21 33 570 572
86 15 570 578
79 58 570 582
11 31 570 582
84 76 570 571
67 53 571 578
12 99 572 573
67 29 572 576
91 64 572 576
51 84 572 588
30 71 572 575
74 34 572 580
14 86 572 574
92 16 573 595
60 91 574 576
59 68 574 580
86 42 574 590
77 17 574 584
25 91 574 578
66 86 575 584
51 51 575 577
92 47 575 582
79 88 576 588
47 40 577 584
16 29 577 588
70 61 577 582
70 82 577 583
30 62 577 579
66 84 578 582
28 63 579 580
13 53 579 589
85 32 579 588
11 19 579 583
90 38 579 580
97 37 579 580
35 89 579 591
17 76 579 593
11 59 579 581
23 19 579 586
88 17 579 587
61 82 579 580
19 38 580 582
36 47 581 585
61 45 581 586
25 34 581 584
96 85 581 587
81 93 581 591
36 63 581 582
80 33 581 582
15 93 581 583
20 74 581 588
28 14 581 587
11 35 582 598
93 65 583 584
73 90 583 591
78 44 583 584
18 30 583 610
34 31 583 601
84 73 583 584
48 34 583 584
77 100 583 599
56 72 583 599
81 57 583 584
58 14 583 587
40 68 583 591
57 97 584 585
98 40 585 596
81 99 585 595
12 25 585 593
66 44 585 594
92 40 585 592
58 74 585 603
68 43 585 586
35 72 585 602
16 89 585 590
88 36 585 618
69 15 585 586
73 96 586 589
26 48 586 594
47 92 586 600
51 44 586 595
91 20 587 592
99 77 588 594
77 80 589 602
16 60 589 590
47 98 589 595
68 98 590 591
51 71 590 592
53 69 590 595
12 31 591 613
30 67 592 595
34 49 592 597
64 90 592 607
36 86 592 595
48 57 592 605
94 13 592 617
92 16 592 593
88 10 592 606
94 57 592 604
90 72 592 628
29 86 592 608
91 59 593 604
89 60 593 597
46 98 593 596
22 68 593 594
96 82 594 596
72 68 594 603
13 32 594 599
24 97 595 620
65 82 596 598
38 49 596 606
53 43 597 601
84 34 598 601
52 80 598 603
84 61 598 604
50 31 598 603
12 91 599 600
89 75 599 600
11 23 600 601
37 87 600 609
25 11 600 619
74 49 600 601
23 14 600 607
98 35 600 601
55 32 600 606
95 48 600 604
71 54 600 603
77 17 600 610
64 88 600 603
91 52 600 616
99 27 601 607
83 32 602 606
97 70 602 605
41 45 602 610
79 100 602 628
43 55 602 613
86 90 602 608
26 61 602 603
38 29 603 630
24 52 604 612
86 80 605 610
27 86 605 612
86 15 605 610
56 63 605 610
86 10 605 606
65 65 605 620
83 83 605 611
67 66 605 609
22 42 605 615
83 61 605 608
76 66 606 614
13 63 607 611
25 49 607 639
50 81 607 610
56 67 607 611
89 95 607 608
91 11 607 610
16 13 607 615
28 71 608 625
83 75 609 613
48 27 609 617
61 16 609 612
25 99 609 610
83 80 609 620
76 58 610 624
63 52 611 616
16 76 611 623
20 11 611 618
72 47 611 614
96 94 611 629
17 26 612 616
61 22 612 615
33 50 612 615
10 57 612 620
50 32 613 629
10 44 614 622
44 21 614 621
60 82 614 620
18 95 614 617
55 25 614 665
98 78 614 620
64 70 614 625
30 40 615 631
52 79 616 628
30 49 616 620
36 34 616 620
69 100 616 627
19 75 616 617
19 97 616 654
34 13 616 626
56 100 617 621
86 83 618 628
23 60 618 624
88 96 618 628
86 63 618 619
19 65 619 621
79 18 619 622
95 20 619 623
64 80 619 634
44 22 620 634
67 71 621 622
32 100 621 627
18 28 622 634
56 51 622 627
79 70 622 636
59 48 622 629
69 33 623 630
99 44 624 631
38 81 624 625
23 29 624 633
81 62 624 628
44 23 624 626
91 77 624 644
95 75 624 631
21 56 624 639
30 89 624 633
33 37 624 631
26 82 625 642
63 67 625 627
17 71 625 631
70 92 625 626
81 89 626 634
43 67 626 630
64 91 626 631
80 27 627 634
10 17 627 634
93 58 628 632
23 90 629 646
58 30 629 643
21 92 629 631
95 38 630 634
92 70 630 646
56 93 630 631
28 58 630 631
59 88 630 632
33 74 630 631
75 37 630 647
42 82 630 667
41 98 630 632
14 39 631 656
62 50 632 650
49 73 632 660
19 45 632 636
61 57 632 633
28 32 632 642
38 22 632 637
31 17 632 647
37 75 632 634
29 28 632 647
18 43 633 635
59 17 633 634
11 27 633 636
84 76 633 641
51 98 633 635
44 61 634 648
90 79 635 638
17 49 635 637
82 39 635 637
63 33 636 653
98 85 636 639
50 88 637 641
59 24 637 643
74 35 637 645
66 30 637 638
36 46 637 639
77 59 637 644
59 61 637 641
22 11 637 639
54 32 637 640
88 29 637 648
90 68 637 638
10 85 638 650
99 50 638 640
56 46 638 639
15 82 639 642
28 77 640 651
32 28 640 642
22 27 640 643
19 25 640 661
33 98 640 641
90 74 640 649
31 92 641 647
70 11 642 646
17 38 643 644
18 32 643 653
60 88 643 645
28 100 643 651
52 20 643 648
17 67 643 662
34 70 643 645
23 62 643 653
11 63 643 672
89 72 643 658
76 51 644 656
54 78 644 649
20 67 645 650
76 66 645 655
91 17 646 652
30 17 646 658
46 60 646 647
50 39 646 657
74 28 646 647
22 38 647 655
61 76 648 656
51 98 648 653
33 15 648 652
90 53 648 686
70 89 648 657
64 32 649 654
15 61 649 668
41 99 650 656
99 42 650 652
39 97 650 663
54 45 651 656
99 99 651 652
76 41 651 667
76 31 651 656
75 91 652 665
51 84 652 660
14 77 653 654
58 24 654 663
64 98 654 657
61 90 654 673
55 47 654 670
31 76 654 655
26 29 654 677
18 96 655 667
26 55 655 656
73 79 655 656
78 14 655 658
77 91 655 656
29 68 655 656
20 34 655 674
36 16 656 659
59 99 657 667
67 69 657 666
89 50 657 659
81 84 657 663
80 13 657 661
27 26 657 658
57 40 657 669
49 64 657 665
63 45 657 667
28 66 657 663
32 43 657 661
81 78 658 660
67 60 659 692
15 49 659 664
32 65 660 663
47 73 660 673
83 38 661 671
53 19 661 695
44 29 661 667
67 45 661 662
16 78 661 662
64 46 661 666
85 64 661 662
50 93 662 671
10 86 662 668
73 59 662 664
36 32 662 665
26 38 662 663
24 63 663 668
86 41 664 688
81 10 664 675
35 34 664 667
91 82 664 686
92 32 664 666
28 23 664 667
22 56 664 670
72 98 665 694
100 83 666 667
48 26 666 682
98 75 666 667
59 62 666 690
68 45 666 667
64 34 666 681
44 99 666 674
94 34 667 675
50 89 668 682
91 24 668 672
27 65 668 679
88 51 668 673
53 29 668 669
59 26 668 670
58 74 668 671
84 95 668 674
75 10 669 674
22 30 669 682
17 90 670 688
87 61 671 681
36 53 671 681
29 47 671 680
35 97 671 691
84 85 671 702
72 92 672 680
90 32 673 675
98 50 673 685
84 84 673 676
11 45 673 684
29 48 673 674
31 28 673 677
91 98 673 676
45 12 674 676
76 84 675 678
13 52 676 679
87 65 676 690
21 49 677 680
44 95 677 680
10 10 677 684
91 83 677 680
15 74 677 678
28 73 678 708
64 98 678 684
35 42 678 680
82 52 679 680
96 47 679 689
24 93 679 680
86 85 679 680
12 24 679 683
61 44 679 692
53 73 679 685
53 28 680 684
84 12 681 688
54 48 681 702
16 89 681 704
63 13 681 692
96 71 681 683
82 11 682 696
20 80 682 683
92 12 682 685
95 61 682 684
88 75 682 684
30 75 682 703
59 57 682 686
70 100 682 689
86 90 682 684
26 30 683 688
13 62 684 711
51 51 685 711
41 77 685 696
94 74 685 686
72 65 685 687
27 40 685 688
62 10 685 698
11 49 685 687
72 18 685 686
30 82 685 687
37 30 685 694
63 12 685 694
45 17 686 697
85 28 687 697
47 10 688 693
29 80 689 690
32 79 689 690
11 91 689 692
91 84 689 701
62 96 689 699
85 89 689 691
87 63 689 692
88 96 690 696
11 94 691 699
83 72 691 693
46 70 691 693
12 27 691 701
96 20 691 698
85 23 691 695
15 89 691 708
20 31 691 701
94 52 691 694
92 58 692 696
35 13 693 694
46 97 693 704
99 21 693 703
48 41 693 697
25 76 693 696
29 100 693 696
15 46 694 696
75 71 695 711
60 86 695 698
79 96 695 698
96 89 695 718
56 42 695 704
38 41 696 708
24 90 697 698
91 56 697 700
11 49 697 700
76 74 697 708
42 83 697 713
78 31 697 698
70 93 697 700
78 19 697 699
53 90 697 704
40 31 698 720
19 84 699 705
11 32 699 710
68 29 699 702
59 38 699 702
74 56 699 708
81 11 699 703
94 73 699 704
84 63 700 704
100 62 700 706
45 99 700 709
54 12 700 712
40 37 701 717
32 68 701 703
31 40 701 708
72 51 701 708
37 33 702 708
11 33 702 704
52 28 703 711
13 93 703 704
14 61 703 717
50 15 703 706
88 71 703 711
20 80 703 705
96 55 703 710
46 23 703 707
56 34 704 713
79 72 705 708
70 68 705 711
18 86 705 709
82 33 705 708
23 82 705 710
62 36 705 706
65 42 705 707
71 27 705 711
56 29 705 719
11 28 706 707
51 31 706 711
32 54 707 709
69 28 707 717
45 29 707 722
12 80 707 708
66 14 708 711
48 23 709 710
91 94 709 713
42 10 709 719
65 23 709 713
42 36 709 712
18 54 709 717
30 89 709 715
85 80 709 722
11 53 709 720
18 93 710 711
38 85 710 712
77 61 710 713
80 59 710 711
84 12 710 744
91 16 710 718
45 29 710 723
11 95 710 715
44 22 711 724
40 16 712 717
42 38 712 719
25 51 712 717
26 42 712 714
77 64 712 716
26 100 712 729
62 44 712 719
40 81 712 713
21 90 712 713
60 58 712 716
80 62 712 714
19 63 713 726
58 29 714 719
71 81 714 717
32 79 714 719
70 31 715 717
84 96 715 717
65 57 715 735
59 27 715 719
19 62 715 722
15 69 715 722
41 15 715 716
71 85 716 721
100 98 716 739
28 42 716 735
17 18 716 722
41 19 717 728
25 76 718 720
38 40 718 740
94 32 718 743
11 70 718 730
82 65 718 735
62 23 718 731
61 55 718 726
90 61 719 730
71 16 720 721
39 51 720 722
25 56 720 724
83 21 720 724
57 12 720 721
10 91 721 731
13 41 721 723
58 53 721 734
54 39 721 722
22 96 721 724
46 12 721 722
71 16 721 722
78 100 721 729
86 25 721 722
53 60 721 732
74 16 722 724
79 94 723 739
17 60 723 733
80 97 723 725
85 57 723 734
80 73 723 724
30 18 723 737
31 61 723 731
54 19 723 730
52 89 723 726
30 84 724 725
97 17 725 727
71 51 726 736
98 22 726 727
94 89 726 748
89 99 726 727
80 23 726 747
64 75 726 733
94 99 726 729
57 40 727 728
97 77 727 728
66 87 727 751
13 11 727 728
100 23 728 738
57 85 729 733
100 85 729 739
68 17 730 742
54 54 730 735
77 55 730 739
20 33 730 737
53 28 730 736
56 55 731 734
23 75 731 732
68 11 732 763
91 83 732 733
94 100 732 739
50 71 732 741
56 90 732 739
66 75 732 733
57 13 732 743
40 65 732 740
27 100 732 751
25 86 733 755
39 49 734 735
82 46 735 744
98 64 736 752
55 65 736 742
48 99 736 738
25 85 736 765
60 88 736 737
22 49 736 739
88 32 736 738
95 61 737 756
76 39 737 741
58 73 737 747
69 22 737 744
92 61 737 739
32 52 737 744
64 71 737 738
80 79 737 755
26 41 738 740
74 96 738 745
11 73 739 743
89 66 740 749
48 96 740 746
27 39 741 742
27 50 741 745
59 96 742 749
39 84 742 756
15 73 742 755
59 73 742 750
19 85 742 769
52 25 742 746
82 60 742 744
92 44 742 761
65 12 742 746
43 100 742 758
80 97 742 747
48 17 742 745
55 71 743 744
59 67 744 752
91 95 745 752
72 79 745 748
25 10 746 760
78 97 746 769
68 26 747 767
64 63 747 757
29 57 747 765
33 39 747 748
74 85 747 748
66 92 747 757
89 60 747 750
11 97 747 761
71 92 747 749
49 13 747 748
97 11 747 757
79 75 747 751
14 40 748 757
68 57 749 760
42 59 749 762
50 18 749 757
71 98 750 757
96 67 751 761
45 19 751 769
18 89 751 755
96 16 751 752
15 53 751 753
81 61 751 759
28 48 751 754
43 23 752 753
87 84 753 754
46 35 753 761
32 35 754 756
31 42 754 763
30 15 755 759
100 21 756 761
19 33 756 764
60 61 756 758
34 37 756 763
19 56 756 769
95 15 756 766
92 33 756 757
40 69 756 758
75 74 756 762
23 67 756 759
96 36 756 759
95 98 757 767
94 86 758 765
64 71 758 769
55 43 758 760
86 22 758 769
29 52 758 769
66 93 758 761
30 75 759 761
24 23 759 767
50 14 759 769
81 40 759 763
19 86 759 761
38 28 759 760
52 70 760 769
37 27 760 761
90 27 760 767
95 42 760 763
40 16 761 769
68 65 762 766
20 66 762 768
34 52 762 769
37 49 762 769
14 77 762 769
56 38 762 769
78 40 762 764
55 31 762 764
31 62 762 769
45 34 763 765
51 27 764 765
10 79 764 769
41 81 764 769
64 94 764 769
71 13 764 768
24 52 764 769
42 81 765 768
36 99 766 767
53 37 766 769
83 47 766 769
83 58 766 769
72 81 766 769
39 86 766 769
72 95 766 767
87 61 767 769
79 45 768 769
27 79 768 769
59 24 768 769
44 53 768 769
24 94 768 769
95 40 768 769
66 17 768 769
18 48 768 769
97 23 768 769
;
%macro SetupData(task_data=, capacity=);
set TASKS;
num capacity=&capacity;
num profit{TASKS}, weight{TASKS}, start{TASKS}, end{TASKS};
read data &task_data into TASKS=[_n_] profit weight start end;
/* the set of start times */
set STARTS = setof{i in TASKS}start[i];
/* the set of tasks i that are active at a given start time s */
set TASKS_START{s in STARTS}
= {i in TASKS: start[i] <= s < end[i]};
%mend SetupData;
%macro ResourceAllocation_Direct(task_data=, capacity=);
proc optmodel;
%SetupData(task_data=&task_data,capacity=&capacity);
/* select task i to come online from period [start to end) */
var x{TASKS} binary;
/* maximize the total profit of running tasks */
max TotalProfit = sum{i in TASKS} profit[i] * x[i];
/* enforce that the shared resource capacity is not exceeded */
con CapacityCon{s in STARTS}:
sum{i in TASKS_START[s]} weight[i] * x[i] <= capacity;
solve with milp / maxtime=200 logfreq=10000;
quit;
%mend ResourceAllocation_Direct;
%ResourceAllocation_Direct(task_data=TaskData, capacity=100);
proc sort data=TaskData;
by start end;
run;
%macro ResourceAllocation_Decomp(task_data=, capacity=, block_size=);
proc optmodel;
%SetupData(task_data=&task_data,capacity=&capacity);
/* split into blocks of size blocks_size */
num block_size = &block_size;
num num_blocks = ceil( card(TASKS) / block_size );
set BLOCKS = 1..num_blocks;
/* the set of starts s for which task i is active */
set STARTS_TASK{i in TASKS} = {s in STARTS: start[i] <= s < end[i]};
/* partition the start times into blocks of size block_size */
set STARTS_BLOCK{BLOCKS} init {};
num block_id init 1;
num block_sz init 0;
for{s in STARTS} do;
STARTS_BLOCK[block_id] = STARTS_BLOCK[block_id] union {s};
block_sz = block_sz + 1;
if(mod(block_sz, block_size) = 0) then
block_id = block_id + 1;
end;
/* blocks in which task i is online */
set BLOCKS_TASK{i in TASKS} =
{b in BLOCKS: card(STARTS_BLOCK[b] inter STARTS_TASK[i]) > 0};
/* minimum block id in which task i is online */
num min_block{i in TASKS} = min{b in BLOCKS_TASK[i]}b;
/* select task i to come online from period [start to end)
in each block */
var x{i in TASKS, b in BLOCKS_TASK[i]} binary;
/* maximize the total profit of running tasks */
max TotalProfit = sum{i in TASKS} profit[i] * x[i,min_block[i]];
/* enforce that task selection is consistent across blocks */
con LinkDupVarsCon{i in TASKS, b in BLOCKS_TASK[i] diff {min_block[i]}}:
x[i,b] = x[i,min_block[i]];
/* enforce that the shared resource capacity is not exceeded */
con CapacityCon{b in BLOCKS, s in STARTS_BLOCK[b]}:
sum{i in TASKS_START[s]} weight[i] * x[i,b] <= capacity;
/* define blocks for decomposition algorithm */
for{b in BLOCKS, s in STARTS_BLOCK[b]} CapacityCon[b,s].block = b;
solve with milp / presolver=basic decomp;
quit;
%mend ResourceAllocation_Decomp;
%ResourceAllocation_Decomp(task_data=TaskData, capacity=100, block_size=20);
%ResourceAllocation_Decomp(task_data=TaskData, capacity=100, block_size=80);