From 4e8ac826929117f95baeb37e1518773d1169d900 Mon Sep 17 00:00:00 2001
From: Mathias Magnusson <mathias@magnusson.space>
Date: Wed, 28 Feb 2024 18:00:30 +0100
Subject: Random uncommited stuff

---
 kattis-open/knapsack/gen.py     |    5 +
 kattis-open/knapsack/input      | 2001 +++++++++++++++++++++++++++++++++++++++
 kattis-open/knapsack/knapsack.c |   59 ++
 3 files changed, 2065 insertions(+)
 create mode 100644 kattis-open/knapsack/gen.py
 create mode 100644 kattis-open/knapsack/input
 create mode 100644 kattis-open/knapsack/knapsack.c

(limited to 'kattis-open/knapsack')

diff --git a/kattis-open/knapsack/gen.py b/kattis-open/knapsack/gen.py
new file mode 100644
index 0000000..a5644e3
--- /dev/null
+++ b/kattis-open/knapsack/gen.py
@@ -0,0 +1,5 @@
+from random import randint
+
+print("2000 2000")
+for i in range(2000):
+    print(randint(1, 10000), randint(1, 10000))
diff --git a/kattis-open/knapsack/input b/kattis-open/knapsack/input
new file mode 100644
index 0000000..8da5b64
--- /dev/null
+++ b/kattis-open/knapsack/input
@@ -0,0 +1,2001 @@
+2000 2000
+5400 3089
+6128 2491
+498 6741
+8219 8585
+4105 5344
+4671 4094
+4474 667
+7553 3351
+6472 7896
+6439 709
+9202 2732
+3123 1297
+4233 8144
+1264 6982
+2465 1001
+667 7849
+1017 6817
+5791 8375
+410 9912
+5706 1690
+7106 5074
+7527 2785
+8244 4764
+1893 3918
+1158 3372
+9545 2398
+9668 7311
+9924 6994
+4671 4106
+4454 4360
+7653 6668
+4948 3199
+2513 8484
+8736 7054
+7066 4848
+5823 8214
+1696 8251
+2049 8475
+7858 2823
+8328 6994
+731 5322
+3418 6354
+3846 4431
+8277 4656
+6881 6512
+6634 6532
+680 931
+7718 9186
+5528 216
+5850 3532
+2969 8890
+8999 6180
+9965 8156
+2223 4284
+2798 3
+4105 4772
+1052 8957
+2578 9402
+1221 2985
+428 5227
+6118 5216
+2164 378
+148 9703
+3553 8976
+9512 2829
+896 3743
+9317 424
+9157 9816
+1314 7420
+6485 4019
+8446 3272
+842 638
+9287 1062
+5362 817
+1745 7352
+7989 1661
+6668 5081
+4866 1143
+5366 4077
+3999 5690
+1099 7073
+1025 3253
+1669 8964
+5814 3706
+9403 5189
+8568 6397
+2156 298
+424 4893
+8160 3445
+4250 4756
+4303 521
+8198 6123
+8432 1094
+5033 6098
+732 4678
+2598 4020
+2504 346
+4026 5632
+7911 5803
+6606 5734
+3974 5252
+9556 8219
+427 2819
+2523 8165
+8414 4671
+9405 5521
+6843 2073
+6110 5314
+6885 2277
+9907 4825
+2551 7466
+5228 8017
+9175 5871
+4084 3179
+786 289
+7183 1274
+9208 2325
+5958 7286
+5940 2958
+1469 6887
+4349 7128
+5473 6061
+945 5862
+7305 7756
+5045 943
+2594 4716
+9350 4341
+8527 7916
+766 1342
+1952 4506
+156 6622
+5678 6913
+8504 5373
+5930 7169
+1436 7226
+4544 5506
+451 757
+9973 4004
+3989 2060
+6143 1599
+1252 647
+3025 2973
+3331 1118
+1857 3936
+6760 5932
+4659 9570
+2997 8104
+3252 8174
+3562 4613
+6571 7122
+1165 357
+5782 5987
+1762 8951
+664 4187
+4411 5866
+562 9815
+3417 5505
+1902 8635
+7987 4039
+4683 272
+2387 627
+7435 9837
+1409 7431
+3040 3823
+3520 3113
+3552 3401
+7893 5896
+3505 6972
+5707 4991
+6552 5657
+3199 4966
+4634 4191
+1209 1380
+7811 5904
+8169 5149
+9937 787
+1025 3393
+1905 8977
+1949 8761
+8961 8335
+3702 4772
+3504 9944
+1915 5335
+760 8166
+7402 4857
+9934 9795
+3490 6973
+8372 7734
+224 2204
+9264 3131
+4962 199
+7875 220
+5995 6288
+9003 8210
+9496 3583
+2854 6306
+2056 3395
+8363 1122
+2428 9824
+2646 5102
+7524 3584
+6388 3910
+2929 5683
+6267 6369
+9645 2812
+1660 5310
+7951 9991
+8424 4726
+8980 8142
+7445 6394
+6884 581
+8928 9529
+136 5229
+4041 8848
+68 4517
+5165 2905
+3 3107
+2354 8158
+6290 840
+2257 5729
+5219 1762
+2495 3853
+3129 4403
+2442 2084
+2092 8326
+2896 4042
+9021 3253
+3946 7595
+8372 8986
+5690 7175
+5335 8818
+6529 8376
+7814 4759
+5359 1185
+1101 4582
+1206 4978
+5643 3604
+5033 724
+7430 8652
+6278 237
+6319 8916
+871 732
+3753 8374
+9995 8500
+2656 6158
+3389 8709
+8586 6661
+2979 9159
+9421 1631
+7333 3348
+6573 2120
+396 6351
+7805 7566
+4076 9126
+7957 7861
+9965 8743
+9978 1601
+9077 9797
+5946 9748
+590 2742
+3856 5054
+8536 2778
+9426 7157
+9060 8786
+9433 7417
+5851 6931
+6277 5491
+8883 137
+7317 1296
+7897 3779
+9522 5355
+1635 7888
+4851 1414
+7244 2840
+4623 9994
+8762 9822
+2702 6380
+4530 8214
+1210 3083
+9580 8262
+3641 9562
+9082 270
+3697 2654
+7692 2728
+3345 775
+3164 501
+2635 9861
+9051 5222
+996 6653
+999 4834
+1169 2510
+7409 6490
+9670 9599
+4063 2849
+8116 8299
+5432 4899
+9869 9141
+1296 8101
+7623 2207
+1633 8616
+1808 7194
+9484 3652
+1982 9122
+597 2211
+1157 1763
+2092 7095
+1584 8309
+5386 5272
+3985 2631
+966 4337
+380 5186
+216 3717
+8807 4631
+9129 8829
+3927 8360
+7715 6985
+1400 6173
+9836 8761
+7055 9439
+6862 2996
+6330 1399
+9760 7366
+4936 9201
+1533 7112
+6076 9379
+2191 5066
+8442 6969
+4265 2675
+6198 3066
+9630 9870
+6118 7465
+4852 7115
+7145 7412
+2472 5384
+58 7339
+4956 1162
+7449 1221
+2026 1358
+4431 3600
+5054 2176
+1409 9343
+4354 498
+7967 9847
+9553 8673
+477 2272
+3403 3042
+1647 9584
+328 9981
+8539 4787
+1480 54
+8593 2327
+4600 9208
+6496 3476
+2334 2745
+6727 8611
+780 7908
+1619 3294
+6401 564
+9870 3830
+2645 6104
+7157 1948
+706 9378
+8192 3748
+9831 4100
+1923 7152
+8046 6960
+4774 8806
+3520 4461
+2453 9699
+2353 1495
+1759 6929
+2937 2336
+5148 581
+4563 5883
+5687 1869
+5932 8352
+1170 2095
+9182 6933
+577 4376
+8309 5806
+1228 8322
+4588 7863
+2862 4141
+56 2805
+6681 1398
+9772 8187
+2157 2625
+9736 7783
+6845 1831
+653 3010
+9662 6822
+1684 5347
+871 8189
+6648 9188
+7853 9944
+7279 5725
+7669 955
+7369 2287
+4142 163
+4906 8132
+1287 698
+4697 9794
+7178 5193
+1577 7147
+5922 8266
+857 159
+4508 1522
+4495 4949
+1870 8623
+1263 7683
+1017 9234
+4352 5345
+5329 5999
+4557 4194
+3061 9126
+2098 8378
+551 1470
+8836 2716
+3898 8632
+3286 4734
+27 3412
+9337 8236
+6703 3985
+9445 2267
+5327 5207
+4533 8401
+9949 5769
+6955 1170
+717 8156
+4504 8582
+2206 8651
+8569 2615
+8923 8674
+3138 8392
+824 6777
+1210 4180
+2486 2779
+2332 6040
+6051 5437
+9485 7853
+7638 9505
+5988 4179
+6601 4932
+8601 4858
+105 6974
+6030 4990
+1950 6847
+9352 8236
+1343 7323
+7349 2169
+220 756
+7979 746
+2961 1622
+3856 4034
+1787 3174
+2948 2545
+9021 3862
+712 2492
+4913 7395
+2263 9228
+6168 8435
+5612 9458
+1767 4569
+845 4751
+5772 9486
+7332 8998
+814 8851
+4653 8775
+332 4482
+3630 9596
+3289 9612
+5188 9346
+2068 1731
+9610 649
+4157 6163
+8922 4086
+8797 77
+8156 8254
+1470 3435
+7957 4634
+5884 1996
+5626 9699
+1168 8976
+6572 4638
+229 1388
+4662 2308
+8290 1786
+6218 8139
+8393 5673
+7545 6426
+6236 7964
+5689 6481
+2705 6221
+889 1953
+1116 2994
+2495 5176
+6422 2622
+8984 296
+1782 6619
+7130 1861
+2315 6457
+1449 6897
+4304 579
+7738 6923
+3231 3746
+9785 7121
+2136 9827
+3881 5636
+8217 2820
+4603 9766
+5630 1261
+9148 7602
+6069 6965
+6917 8749
+7310 4090
+3314 2779
+6788 6321
+955 5655
+8423 5556
+5863 9370
+3902 5282
+4426 2850
+5096 7354
+2135 2159
+5463 5412
+3005 8860
+6005 4029
+3848 8528
+895 7134
+5724 5831
+5632 1461
+6222 1394
+9724 954
+2397 1487
+9978 2208
+6198 7156
+4183 8199
+5913 9298
+1988 3051
+3954 4142
+649 3584
+925 1537
+4886 2630
+5271 3403
+8203 9086
+2295 3606
+8316 2484
+8819 6935
+6598 7515
+6600 1071
+9888 2072
+1639 7964
+1564 4159
+4977 4313
+9076 7973
+5416 4036
+2658 4033
+2693 7267
+5842 8215
+9748 3423
+362 2507
+597 6925
+6353 901
+7636 8945
+4994 3255
+3872 315
+8051 8548
+7839 7399
+8713 6801
+3338 9736
+2990 6036
+4248 2535
+708 1228
+7881 6357
+8944 867
+7239 4463
+9309 6208
+5186 273
+2355 4305
+7624 2514
+790 6792
+5983 986
+8105 9994
+9073 584
+1558 4880
+4104 9494
+4659 5124
+761 9576
+6459 4462
+941 3266
+4795 3792
+2100 2613
+2612 4720
+8977 4714
+5090 1698
+9581 7199
+7692 352
+6473 2552
+5773 3128
+4193 7482
+6924 6756
+5879 3075
+5492 9607
+636 784
+6008 4895
+3070 3235
+190 8862
+7433 3211
+7045 1749
+125 5302
+4183 6051
+6293 9508
+1933 6216
+9900 4495
+6210 7511
+3609 6651
+1852 8729
+1059 6418
+9918 6173
+5178 1037
+6387 2602
+9993 8363
+5196 5447
+5251 9881
+184 9316
+5535 2474
+2807 7366
+9001 1494
+8737 7557
+8501 2679
+7579 634
+1372 5559
+6352 9157
+7414 2856
+3318 4595
+8326 4873
+5969 7893
+3393 3677
+936 8457
+147 1797
+5647 4061
+5760 1445
+2097 5276
+7846 6054
+9580 8346
+1101 5507
+9645 3999
+6133 9528
+5591 1093
+9841 6222
+6234 4899
+4507 7381
+299 496
+3570 5261
+5617 3729
+4927 1425
+3894 1493
+2198 7503
+864 6952
+6240 8924
+6886 6055
+2790 3600
+7640 7539
+278 1010
+6012 3016
+6226 6832
+2534 5192
+2317 4408
+1031 6067
+1631 4000
+7091 4894
+9359 1500
+2693 6906
+9068 8027
+7966 179
+9137 7209
+555 8408
+5760 832
+2663 9480
+8618 4010
+5787 6886
+1902 8780
+9695 6730
+26 816
+7725 8249
+8343 1453
+2415 6261
+2325 4607
+7632 4909
+8116 4517
+5016 5140
+3588 9912
+4862 2233
+6822 4019
+2273 2706
+8691 3442
+6647 8968
+858 3877
+2055 1916
+6850 3553
+5390 4276
+9143 8004
+4835 1919
+2200 7465
+5615 8942
+2645 966
+9662 2518
+9148 9495
+5264 3279
+924 3403
+8489 9478
+5229 8288
+5236 2877
+7820 9128
+6589 9775
+5010 5407
+5878 8520
+2491 3467
+2260 4302
+8280 8857
+1167 5688
+6271 9746
+3474 5958
+6601 8742
+5156 380
+2507 1135
+9693 3867
+6012 9485
+3593 5977
+4026 1930
+6872 2090
+417 1272
+244 5014
+8175 8950
+9577 1419
+9626 7652
+1555 8424
+4131 1637
+3542 922
+7989 4970
+2408 4677
+6585 1426
+8541 5842
+988 2367
+3622 8320
+853 9527
+4309 2851
+6305 140
+3310 8074
+3186 8830
+9480 2479
+1447 267
+6927 2856
+5671 3650
+8673 9866
+7187 5451
+5503 2882
+9475 1095
+2347 4943
+4793 8317
+4720 3319
+1230 7363
+9493 2471
+6062 6001
+6303 5
+497 6952
+6075 9237
+85 4327
+3636 6419
+8028 2844
+9656 6298
+4499 201
+535 4096
+3013 9297
+1673 4931
+1539 1244
+8475 4459
+4306 8170
+4260 4869
+6305 2166
+9058 2281
+170 5610
+5025 5660
+8377 3476
+9011 7648
+3956 6625
+4963 7617
+7267 4999
+3400 280
+3918 3470
+2828 6709
+1374 4984
+8815 3240
+2760 4935
+4993 5166
+8395 1679
+8534 426
+5266 7086
+4175 7995
+2515 7795
+4874 29
+9166 9983
+5674 3050
+5996 335
+9254 3506
+9362 4774
+277 9885
+3705 6507
+8900 9931
+2028 185
+2896 7720
+2883 956
+6651 4282
+196 8702
+8908 6170
+2712 9162
+9003 3934
+7474 7490
+2732 3000
+5124 5844
+7725 5147
+6892 6774
+7645 3681
+6287 6507
+8796 8774
+7986 8678
+3859 1427
+5561 1763
+1598 7400
+6258 4280
+267 232
+5518 8480
+7611 8121
+6149 8886
+6156 7815
+1164 842
+2627 4442
+7287 5040
+437 9160
+1328 9301
+8863 5152
+9702 728
+6259 5177
+978 5147
+4896 4629
+9289 190
+5281 5642
+6778 2397
+2633 5126
+4262 8090
+8153 3576
+603 1307
+5390 1131
+1226 4849
+3879 6836
+2915 6211
+9409 8393
+9130 4162
+84 2646
+2805 5513
+4277 4101
+7607 1635
+7800 5650
+2278 8061
+3584 2195
+7712 7988
+5979 8250
+8524 1700
+1104 8632
+4510 9661
+4484 5629
+8064 6075
+9535 9666
+2790 9932
+3546 6239
+4699 5864
+3630 6264
+8321 9834
+1788 9639
+1309 3849
+4107 8742
+4669 9573
+5609 2125
+9516 8591
+1525 7457
+8531 6940
+2020 7207
+8689 5957
+4916 6870
+7634 8766
+5553 9209
+7259 6922
+412 336
+1558 2102
+5269 2379
+2674 1859
+2535 2346
+5119 9629
+3463 5696
+2442 4406
+6123 3349
+7520 1417
+1557 4726
+2499 5262
+591 4286
+9819 6976
+5209 3622
+890 1809
+1387 2006
+3873 7944
+2104 1169
+378 3691
+4845 5217
+3233 802
+4821 4095
+8158 6005
+526 5716
+4525 4890
+1900 6408
+2931 1691
+9831 3122
+1223 7262
+4852 6790
+335 5693
+870 4735
+3185 504
+3421 835
+8448 9343
+4332 705
+7518 450
+3160 6097
+4499 4708
+9225 2945
+9526 8957
+5081 7441
+2707 4129
+577 3612
+9734 1515
+5772 4697
+8357 6632
+6711 9676
+793 143
+2516 4072
+3357 8257
+8731 7007
+4223 3340
+8695 747
+8261 5143
+7358 3515
+2975 893
+7370 965
+6536 9869
+6089 8437
+7067 1029
+1927 8829
+7442 446
+5270 2455
+8100 4064
+4369 9210
+8192 1524
+7031 1664
+8581 2464
+5245 3732
+6444 6217
+9810 7906
+9472 3647
+7856 9776
+3127 18
+2254 5322
+3680 2648
+7823 3844
+8348 8717
+8095 809
+3400 3971
+4892 3998
+6158 8952
+9422 4173
+6969 1205
+4963 4913
+3871 8977
+2002 4676
+7837 1880
+6336 1953
+6147 4833
+5396 9240
+297 1884
+5419 7829
+2732 2661
+9090 9480
+6905 6999
+7157 3199
+186 7980
+6441 4815
+7547 5551
+5039 1714
+3446 7125
+5520 4739
+4613 1161
+8414 2269
+7474 1891
+8464 2833
+5831 4771
+342 4379
+7055 1673
+4603 1222
+3773 2634
+2131 3256
+3595 1629
+3746 1515
+5847 263
+5646 2338
+6011 5603
+9036 9830
+4689 4318
+5407 941
+5334 9214
+9884 4555
+6292 1128
+2209 5878
+9689 9284
+3201 7386
+945 6047
+4574 5656
+6783 9752
+1887 4445
+8902 3007
+560 8688
+9013 9856
+1003 8943
+5717 5853
+2639 7893
+3612 9660
+2521 7252
+1405 4011
+1013 2372
+2734 2867
+3175 1031
+7222 2539
+6676 6754
+6955 2449
+7952 4850
+3184 3338
+5892 8512
+3447 1925
+5612 9715
+5631 3876
+5233 1243
+6771 1630
+6397 1937
+2698 8779
+267 7910
+764 4968
+3149 3589
+9498 2617
+1402 1457
+1991 4109
+8717 709
+3427 8891
+9777 8546
+8746 157
+4570 6072
+4312 1271
+3604 2413
+5190 3791
+742 1134
+1652 4107
+4859 218
+88 5546
+7480 8842
+1555 9184
+6874 9202
+5162 1904
+2171 6372
+7505 2346
+1015 6725
+8828 985
+5038 6316
+5991 9256
+8206 4861
+679 9894
+3091 6156
+3803 6648
+2907 7617
+2199 2264
+6826 1980
+1032 7876
+3353 3821
+4161 229
+2781 7648
+1146 2955
+1856 6792
+6656 421
+6753 9436
+7827 9841
+2060 4694
+9417 3635
+8039 1467
+3914 6612
+2584 9997
+9312 4821
+8274 2399
+5049 8532
+4362 4154
+1713 4176
+1565 6832
+8573 4729
+7269 809
+5960 1057
+9609 8093
+2924 9865
+7677 9084
+8224 5723
+4680 6365
+5983 8092
+1448 2774
+1305 274
+7219 7399
+6706 8937
+1210 7204
+3321 5327
+4172 1793
+5477 6521
+2997 6068
+9446 297
+4613 4845
+593 4653
+5573 1815
+6786 3312
+2369 6079
+7246 8310
+1209 9459
+9636 4718
+8086 6875
+2785 5898
+3101 8643
+7025 3590
+1579 9079
+6383 1452
+6523 9774
+8827 6207
+7470 1075
+3206 9527
+8771 9589
+8046 1074
+9578 2874
+7458 3355
+560 9594
+7292 317
+3588 5233
+4874 6167
+3652 8147
+9861 8168
+9728 8864
+5335 6156
+6182 7846
+8835 1593
+1877 4208
+7198 6511
+2069 4867
+8499 6912
+6353 7941
+2554 1160
+6117 1928
+6127 4303
+3039 284
+177 3307
+7433 6189
+9869 1358
+5450 4556
+1508 9241
+8259 2662
+5039 3603
+7336 8928
+3217 6498
+1793 1287
+9104 6349
+7910 128
+4413 1235
+6330 6347
+1439 9053
+5382 4581
+4834 646
+4233 3339
+4490 3075
+2129 2944
+5062 2031
+9260 5913
+3364 2340
+7690 1501
+6745 9034
+8881 3576
+6034 9749
+6739 5304
+4074 3777
+8330 7173
+1587 6784
+6865 653
+6068 513
+9983 9639
+5798 7518
+407 9604
+6535 942
+8095 8086
+2956 2630
+4635 2515
+515 8841
+7432 6539
+3926 1868
+5378 9141
+5273 5966
+202 3438
+2373 7011
+2200 6475
+969 1094
+490 5559
+6281 7130
+8581 7316
+8574 2026
+8870 7635
+8089 2432
+8780 5784
+714 5914
+7099 3324
+1873 9249
+5808 8466
+1348 5967
+8389 5303
+1822 5729
+7716 1874
+2270 8706
+3702 8380
+514 5867
+1399 5582
+8168 6900
+5021 6031
+7834 1016
+7968 4038
+6738 1046
+4956 741
+1668 525
+8115 9136
+9291 6438
+1610 3968
+7014 6776
+152 6519
+2597 2182
+9032 4234
+3912 8086
+4115 4303
+5994 4425
+3335 4491
+5074 1970
+3529 5954
+1862 5865
+5729 4837
+4067 41
+7174 7390
+9674 3891
+7 2064
+3485 6424
+7401 24
+4484 6525
+8233 5503
+8643 5699
+3874 1103
+4920 9155
+9046 8374
+3963 2959
+9240 5396
+5631 1351
+7608 8252
+5129 9415
+8062 3877
+761 4600
+1401 3198
+6668 5250
+3852 2580
+5903 1266
+4417 2192
+5029 3019
+7307 5190
+6719 2803
+3011 3774
+9860 9950
+6468 2568
+434 7114
+4586 2678
+2904 3821
+3496 4705
+6569 3901
+208 7788
+3062 9494
+787 5379
+2983 7357
+1305 7368
+8494 4870
+2899 4032
+6074 4030
+8327 2110
+1505 7975
+3305 7404
+3671 5376
+8188 3651
+2079 7098
+1143 4435
+6277 5719
+5396 6632
+3576 7307
+6145 2520
+935 6355
+3461 8663
+1574 5555
+4505 9731
+9755 9580
+2949 1492
+2506 5336
+5061 5609
+2825 274
+4278 357
+6932 2537
+3710 1743
+5692 2956
+7547 7452
+9994 9146
+6819 7677
+3562 6575
+553 4563
+3730 2931
+2993 842
+1186 9840
+2441 9993
+1059 6842
+3220 6916
+2300 8313
+3415 8746
+8770 4864
+3763 5026
+5295 8103
+8278 2789
+1264 2034
+2320 4719
+8656 4573
+5859 5111
+2161 1636
+8967 79
+7419 8334
+7878 1999
+3538 8128
+4638 2070
+2441 3074
+5221 2440
+6099 1937
+2841 7262
+6639 555
+1412 5999
+6722 5590
+2226 1684
+5823 5773
+8076 1783
+6904 8265
+7995 1834
+2794 357
+2268 9744
+5411 6931
+775 6652
+7387 3968
+2031 8102
+8425 3899
+3277 1875
+5565 3091
+1011 7535
+8968 3678
+4791 6408
+5510 9246
+9717 6497
+8662 8273
+8598 9286
+3786 7371
+4509 8182
+4312 4348
+4701 4139
+9966 4917
+9976 8222
+3846 6878
+430 2447
+6791 1850
+3990 4523
+7579 585
+4074 9593
+9961 832
+2453 1596
+3818 2826
+9207 898
+4223 7339
+4251 1331
+8568 8941
+3248 3778
+7733 1475
+9030 3565
+759 4261
+9660 4296
+7829 661
+5642 4358
+6267 5073
+19 2656
+9273 4381
+3371 7951
+5118 5185
+9792 3574
+2580 4330
+6182 4876
+9897 6290
+5025 7557
+1931 5483
+2878 7216
+8550 3193
+5681 5751
+1470 6685
+9491 1248
+4451 3985
+8362 8558
+4976 5551
+2371 2781
+5486 4701
+5193 8986
+2227 886
+3123 5934
+2697 3275
+4731 2916
+2658 801
+4953 6988
+8847 985
+9919 2218
+6873 1789
+236 9085
+6309 1719
+1453 4680
+1667 2953
+4841 4356
+1841 9363
+9895 6449
+2284 4896
+9698 4132
+8411 933
+6695 6602
+7449 6872
+7664 1616
+8218 7366
+7110 7620
+9739 2922
+3174 6805
+6311 6570
+5174 8720
+4377 4554
+457 1828
+9148 3469
+4018 503
+9560 3921
+5136 5181
+9246 158
+3584 4885
+2381 967
+2875 7525
+1046 7419
+904 8231
+4517 7999
+2825 2461
+1791 6587
+2611 8423
+9808 3793
+5194 2844
+8009 4649
+2204 6335
+610 2595
+7704 3448
+1806 5215
+65 1624
+4497 9915
+999 4727
+560 2859
+5266 321
+6632 107
+5769 5282
+2767 3172
+9293 1735
+599 3633
+1388 3001
+7917 3274
+3612 2280
+2607 5705
+1617 3426
+4814 9102
+7909 4729
+9203 253
+2436 9013
+9788 8680
+7271 9783
+239 9662
+8225 6997
+1648 5407
+7268 9266
+1010 1762
+3340 8686
+9781 3650
+3891 2620
+710 5802
+4929 9399
+3614 4467
+8644 2287
+9039 1901
+4962 2480
+1090 6993
+3160 6206
+4889 5571
+2371 242
+8622 8912
+5039 526
+5853 1316
+9514 87
+741 9103
+3492 6334
+8835 5458
+4646 1944
+7071 5422
+3550 3156
+2073 4154
+8519 8632
+9307 3551
+2293 8112
+1251 2699
+536 3082
+6022 551
+7011 5803
+5400 259
+9884 3461
+4886 7371
+3968 9189
+9907 7226
+8834 5837
+6835 1886
+9979 2786
+6559 9955
+8219 6386
+2810 9508
+4082 6883
+1321 7756
+516 7026
+1646 7946
+2872 8662
+828 3724
+7009 8125
+7578 1787
+5794 1095
+5963 9296
+6546 4093
+6157 5078
+3815 3840
+7543 1402
+4300 9099
+7979 9097
+9924 3041
+8437 4845
+8351 8033
+9733 1504
+6758 9341
+9178 8725
+304 4688
+6870 6180
+2641 336
+7902 5729
+7539 1396
+1258 8579
+6156 136
+1221 8621
+5948 2974
+473 116
+7817 220
+3004 2973
+7084 8842
+4261 9975
+6402 5360
+1927 764
+6126 7904
+7154 8581
+9564 8079
+5888 8645
+5538 6738
+3155 4477
+2533 1236
+3625 2531
+748 5674
+1312 7826
+5963 5814
+7687 4832
+1763 6740
+9189 2933
+9812 1213
+2540 5413
+5701 4896
+3110 3165
+6680 1012
+9918 5388
+6215 3081
+2661 7614
+3652 1522
+952 9111
+378 8142
+8653 1602
+2935 1193
+4964 2105
+3174 5820
+8492 493
+1077 6072
+2768 5694
+2994 6826
+5875 5863
+3448 1764
+6709 2845
+242 5064
+506 2869
+9281 9086
+503 3637
+1539 3869
+9249 2010
+1953 355
+4275 4878
+1165 3206
+1872 3360
+4783 3644
+2475 8761
+3631 5481
+3176 4623
+3046 9621
+5952 4024
+2549 5459
+521 9018
+2563 3425
+2995 2419
+5842 3887
+7487 1118
+549 4215
+2393 4372
+4555 8011
+6286 2851
+5424 4705
+3331 2854
+752 8492
+1810 6533
+9630 6036
+1398 5266
+8324 7483
+8539 5492
+1863 7661
+5872 1524
+3131 4315
+2013 8725
+5715 6799
+7259 1796
+6629 1851
+2719 8846
+515 8973
+2992 8129
+3046 5519
+4741 3288
+4732 4090
+9713 7472
+1162 9472
+5218 1488
+7941 1816
+105 7840
+9933 8710
+347 2506
+6366 3561
+2323 7125
+3797 8348
+836 7852
+7003 4758
+9180 8210
+4180 8087
+7108 5783
+3004 126
+3227 2950
+6092 7647
+2870 4430
+8684 701
+4077 4475
+1769 3394
+1146 8630
+3908 3410
+8807 5592
+3308 7275
+961 625
+2596 9492
+1694 649
+2110 2642
+3498 6495
+9735 2657
+1690 1784
+9549 4052
+1150 4857
+2339 9925
+7767 6654
+7733 2990
+1883 7605
+6192 8963
+6822 3732
+2470 3309
+645 85
+2451 7522
+364 8067
+9870 9792
+8663 5145
+7470 4306
+2372 4404
+8717 3413
+2667 2081
+7147 8579
+30 9489
+1823 4883
+8886 2603
+6610 4911
+118 1779
+4206 7843
+4267 830
+6491 3597
+3700 5127
+9094 5740
+6223 510
+9112 5008
+9871 9874
+7587 9004
+7014 8889
+9112 9952
+4624 6270
+8513 766
+4963 7616
+7660 3957
+9856 8689
+5149 5449
+8065 8021
+6028 3110
+183 7759
+929 7056
+6380 9305
+9003 3192
+7869 445
+8360 9161
+2474 3460
+2847 7006
+8310 9676
+6438 8937
+3978 5962
+4482 8310
+8391 6755
+4832 7910
+7988 3117
+6294 7185
+1087 6203
+2088 8332
+8356 6412
+9882 5975
+6014 9099
+2222 4960
+9448 2348
+4921 2715
+21 936
+8598 2568
+2599 1121
+3617 8530
+7544 6677
+5886 5131
+6083 238
+5494 3963
+8166 1003
+2262 1057
+9724 6799
+8552 8664
+1001 1571
+6306 5496
+218 4489
+5901 7829
+6768 5853
+4660 6910
+2978 2405
+9614 7097
+573 1295
+586 9649
+8031 6340
+6560 8953
+3275 2432
+1002 1198
+4171 5979
+1087 4498
+5514 5170
+8041 1059
+4854 3305
+1601 5232
+7617 916
+475 4110
+8065 2207
+6956 8458
+6311 7642
+1618 4121
+3846 5955
+443 8262
+2503 3291
+8217 5575
+4142 8602
+9942 7203
+285 9458
+4536 9886
+7587 2734
+9258 2046
+2208 163
+1263 3040
+3689 9470
+6298 8161
+9843 3684
+3369 6830
+2482 1982
+209 911
+6748 1043
+8378 7710
+8479 611
+9731 5008
+4793 3235
+9268 3156
+7732 4981
+615 8643
+1288 7034
+4812 879
+4954 6805
+3031 2705
+9020 2591
+5246 4817
+2839 6631
+2545 1097
+3170 224
+5180 157
+152 191
+9796 9708
+8845 8331
+8015 3672
+9082 5542
+9189 489
+6123 3605
+440 6516
+3194 5598
+1025 8228
+1131 2383
+5989 7391
+6090 9394
+9343 6022
+1993 4165
+9249 7255
+5684 1997
+8929 8285
+6464 121
+3046 9088
+9360 557
+141 5282
+4497 1569
+4722 7628
+2248 878
+406 3929
+6463 1965
+4763 526
+297 79
+1764 1544
+9459 9580
+1258 8256
+609 8961
+3324 2926
+7432 7764
+541 8133
+4257 7095
+8156 6983
+9976 3706
+9935 8043
+6667 320
+7161 4810
+2427 7240
+7619 8229
+9591 4251
+6134 5245
+3737 5700
+2661 8865
+7874 1631
+7419 9810
+2888 4374
+4111 1819
+1805 4976
+9971 7982
+4250 2841
+9548 8969
+7689 129
+6443 8209
+459 5760
+8324 4294
+5568 8121
+995 4980
+5635 8155
+2496 9241
+1195 5094
+3390 5514
+8548 742
+6425 6904
+9746 1716
+4583 7172
+7472 3407
+1457 9278
+6839 4030
+6602 2616
+4965 3114
+7029 4119
+3544 1899
+4852 1231
+3712 3573
+2612 4238
+8973 1800
+6110 2176
+9747 1831
+4385 5469
+1592 6188
+9763 9962
+2923 8518
+191 6313
+3252 2020
+7469 4971
+170 6040
+9131 9139
+7960 6728
+879 5605
+5718 7022
+4344 9304
+8241 5316
+3165 4381
+7001 7508
+9903 2120
+6482 9969
+3233 8047
+4129 5650
+3597 6146
+9334 9091
+2371 833
+6825 9773
+3189 7729
+8812 6938
+7155 4561
+893 7461
+2790 2379
+8335 4321
+1481 5439
+4536 9542
+3501 7515
+271 8130
+4405 4697
+8963 1699
+3698 7121
+8095 6326
+9920 7071
+6218 5703
+1292 5997
+2900 3401
+8682 2479
+2552 6204
+277 2476
+4282 4159
+7831 7892
+6172 8545
+6326 1366
+3274 6605
+7354 2111
+8873 1919
+1286 9151
+9841 2610
+8872 2087
+5229 57
+2443 3539
+9000 8824
+8423 8803
+4288 6627
+6804 2688
+2800 5004
+9507 4570
+8802 1740
+8704 5413
+8027 2160
+4430 922
+6667 3264
+9624 3645
+7315 1665
+7370 4376
+2036 9711
+7872 2594
+6684 3460
+38 6783
+1300 6649
+3393 1196
+2997 6316
diff --git a/kattis-open/knapsack/knapsack.c b/kattis-open/knapsack/knapsack.c
new file mode 100644
index 0000000..407b133
--- /dev/null
+++ b/kattis-open/knapsack/knapsack.c
@@ -0,0 +1,59 @@
+#include <stdio.h>
+#include <stdbool.h>
+
+int max(int a, int b) {
+    int v[2] = { a, b };
+    return v[b > a];
+}
+
+int min(int a, int b) {
+    int v[2] = { a, b };
+    return v[b < a];
+}
+
+int ks[2001][2001], v[2000], w[2000];
+bool t[2001][2001];
+int main() {
+    int c, n;
+    while (scanf("%d %d", &c, &n) == 2) {
+        for (int i = 0; i < n; i++) {
+            scanf("%d %d", &v[i], &w[i]);
+        }
+
+        for (int j = 0; j < w[0] && j <= c; j++) {
+            ks[0][j] = 0;
+            t[0][j] = false;
+        }
+        for (int j = w[0]; j <= c; j++) {
+            ks[0][j] = v[0];
+            t[0][j] = true;
+        }
+
+        for (int i = 1; i < n; i++) {
+            for (int j = 0; j < w[i] && j <= c; j++) {
+                ks[i][j] = ks[i - 1][j];
+                t[0][j] = false;
+            }
+            for (int j = w[i]; j <= c; j++) {
+                int skip = ks[i - 1][j];
+                int take = ks[i - 1][j - w[i]] + v[i];
+                ks[i][j] = max(take, skip);
+                t[i][j] = take > skip;
+            }
+        }
+
+        int taken[2000];
+        int taken_count = 0;
+        int j = c;
+        for (int i = n - 1; i >= 0; i--) {
+            if (t[i][j]) {
+                taken[taken_count++] = i;
+                j -= w[i];
+            }
+        }
+        printf("%d\n", taken_count);
+        for (int i = taken_count - 1; i >= 0; i--) {
+            printf("%d%c", taken[i], i == 0 ? '\n' : ' ');
+        }
+    }
+}
-- 
cgit v1.2.3