day3_part2.rb

input = " 785  516  744
  272  511  358
  801  791  693
  572  150   74
  644  534  138
  191  396  196
  860   92  399
  233  321  823
  720  333  570
  308  427  572
  246  206   66
  156  261  595
  336  810  505
  810  210  938
  615  987  820
  117   22  519
  412  990  256
  405  996  423
   55  366  418
  290  402  810
  313  608  755
  740  421  321
  255  322  582
  990  174  658
  609  818  360
  565  831   87
  146   94  313
  895  439  866
  673    3  211
  517  439  733
  281  651  582
  601  711  257
  467  262  375
   33   52  584
  281  418  395
  278  438  917
  397  413  991
  495  306  757
  232  542  800
  686  574  729
  101  642  506
  785  898  932
  975  924  106
  889  792  114
  287  901  144
  586  399  529
  619  307  456
  287  508   88
  159  175  190
  195  261  148
  348  195  270
  905  600  686
  847  396  680
   59  421  879
  969  343  600
  969  361  585
   95  115  209
  512  831  395
  172  774  662
  372  396  290
  957  281  445
  745  525  297
  489  630  225
   81  138   18
  694  114  404
  764  196  383
  607  861   94
  896   92  140
  786  862  123
  389  449  298
  795  339  780
  863  507  892
  589  850  759
  273  645  371
  368  884  486
  637  553  423
  391  630  950
  442  950  581
  383  650  712
  538  844  405
  353  261  544
  682   60  336
  750  308  698
  177  369  643
  479  919  137
  482  598  184
  275  726   55
  139  874  850
  456  195  839
  385  766  205
  561  751  249
  397  764  714
  508  856  876
  478  410   12
  686  230  267
  876  247  272
  160  436  673
  466  798  278
  487  839  773
  754  780  900
   45  983  801
  800  595  188
  523  408  239
  269  609  216
  745  692  237
   15  588  840
  702  583  298
  707  150  859
  835  750  375
  211  754  368
  892  434  152
  521  659  592
  683  573  904
  902  544  412
  718  218  502
  379  227  292
  482   87  780
  903  433  382
  223  196  369
  824  588  734
  342  396  279
  164  561  918
  409  841  918
  893  409  204
   33  435  169
  858  423   74
  134  797  255
  517  881  109
  466  373  193
  379  180  973
  620  467  941
  260  512  298
  993  461   89
  111  986  990
  946  668  987
   26   65  110
  223   55  372
  235  103  473
  288  244  964
  343  199   25
   62  213  984
  602  117  311
  624  142  356
   65  130  248
  709   95  376
  316  897  723
  420  840  349
  159  460  208
  385  445  929
  408   13  791
  149   92  682
  791  253  440
  870  196  395
  651  347   49
  738  362  536
  392  226  485
  683  642  938
  332  890  393
  954  394  971
  279  217  309
  610  429  747
  588  219  959
  840  565  791
  671  624  380
  384  426  485
  407  323  226
  780  290  428
  539   41  571
  455  267  306
   48  607  250
  432  567  400
  851  507  477
  853  456  923
  615  416  838
  245  496  353
  253  325  926
  159  716  989
  488  216  473
  808  222  742
  395  178  798
  514  383  732
  478  845  728
  508  486    4
  230  643   35
  151  298  584
  123  906  576
  583  682  294
  580  605  784
  624  517  984
  911  778  745
    9  897  325
  913  357  501
   27  221  249
  798  669  614
  824  777  397
  749  461  304
  734  769    1
  447  543  306
  454  200   19
  551  134  674
  562  329  665
  352  188  281
  808  151  622
  834  255  648
  352  199  340
  429  182  121
  585  223  382
  524  977  225
  520  156  532
  827  929  419
  429  175  759
  284  376  877
  312  548  751
  571  507  529
  390  503  483
  710    1  146
  938  421  582
  975  981  186
  118  771  531
  328  490  638
  452  743  750
  511  772  242
  957  850  177
  669  750  665
  975  296  664
  228   35  159
  763  347  650
  752  315  557
  366  530  294
  828  154  645
  730  388  763
  744  298  774
  459  508  375
  449  485  748
  537  819  907
  526  259  551
  773  890  650
  523  839  473
  645  928  485
  333  109  115
  403  952  399
  229   50  606
  377  900  212
  693  731  399
  682  103  579
  441  764  471
  481  114  267
  196  567  591
  353  495  798
  436  348   30
  794   88  526
  926  411  524
    1  862  754
  839  440  848
  839  458  109
  961  799  930
  944  692  853
  168  520  788
  579  920  687
   32  930  283
  575  759  747
  857  705  926
  842  674  925
  233  163   29
  544  409  719
  266  643  767
  315  323   56
  754  135  658
   99  757  569
  818  832  207
  296  602  519
  316  371  301
  409  879  747
  765  696  151
  960  836  689
  526  564  790
   33  954  343
  548  203  379
  545  797  622
  550  122  105
  606  538   12
  686  434  102
  595  820  249
  642  215  221
  120  703  124
  972  440  214
  444  544  447
  963  225  373
  904  628  271
  733  109  374
  193  673  588
  446  724  945
  246  771  901
  389  900  339
  331  323  756
  245  428  969
  565  457  539
  977  743  742
   26  199  543
  960  804  405
  795  914  721
  454  695  816
  984  422  849
  437  495  803
  237  106   58
  221  442  834
  638  278   21
  697  880  830
  818  953  849
  276  335  944
  152  650  953
  232  972   23
  675  991  179
  741  579  408
  164  741  285
  682  156  113
   71  607  759
  740  692  644
  284  229  308
  681  114  133
  961  232  394
  214  653  533
  240  863  332
  115  651  664
  396  356  477
  308  220  134
  283  505  569
  286  400  234
  413  830  734
  534  877  619
  293  562  171
  862  216  186
  819  427   63
  491  121  321
  139  108  142
  438   39  219
  345  120  486
  367   91  482
  400   61  605
  780  858  434
  854  188  478
  141  726   62
  600  904  292
  312  328  103
  648  896  200
  304  299  382
  372  325  229
  625  114  513
   95  742  875
  432   99  818
  510  731  863
  353  520  495
  501  335  400
  411  187  358
  612  274  381
  658  586  774
  908  858  876
  162  722  881
  604  277  772
  677  484  369
  964  772  239
  973  618  388
  463  799  264
  262   49  691
  800  816  875
  827  820  394
  828  682  576
  571  670  724
  322  910  202
   12   72  856
  529  771  829
  520  830   38
  796  154  681
  662  160  750
  193  314  633
  772  925  453
  769  769  427
  318  182  338
  552  366  505
   82  205  468
  486  218  352
  542  633  640
  612  625  879
   69  715  867
  233  571  479
  818  703  639
  866  989  856
  285  504  265
  981  758  773
  920  716  904
  698  390  977
  336    1  838
  563  391  169
  692   87  692
   17   75  754
  691  100  143
  605  754  711
  844  724  864
  261  457  167
  640  655  371
  554  294  874
  777  541  528
  902  595  406
  774  309  254
  322  721  257
  638  883  617
  278  793  525
  779  669  120
  144  539  722
  106  533  242
  187  925  743
  221  863  490
  284  899  481
  186   82  103
  102  143  562
  306  494  540
  352  574  239
  885  218  247
  551  750  123
  859  634  206
  391  513  363
  361  608  410
  390  303   93
  353  111  592
  472  450  724
  395  507  621
  494   19  266
  184  416  881
  330  402  821
  999   82  370
  613  165  722
  572  141  978
  361  202  671
  975  376  474
  878  445  216
  925  529  713
  499  522  338
  891  315  749
  712  539  290
  382  388  479
  806  394  342
  273   56  594
  213    3  226
  359   52  693
  637  612  601
  792  336  253
  223  380  699
  189  101  265
  812  297  699
  635  255  739
  885  653  957
  165  873  646
  883  444  400
  982  789   89
    6  922  192
  990  310  109
  159  595  656
  884  640  514
  876   44  671
  288  569  864
  108  255  977
  237  819  178
  417  923  144
  231  444  375
  452  951  241
  947  724  475
  569  243  481
  646  678    7
  282  474  921
  830  520   36
  961  461  957
  333  955  876
  359  778  909
  128  276   70
  914  961  185
  606  942  453
  373  323  614
  270  170  447
  745  480  454
  499  649   95
  468  127  922
  436  722  121
  202  773  971
  307  127   21
   11  122   90
  305   54   93
  266  543  113
  931  735  706
  931  480  683
  306  433  158
  155   35  379
  343  401  321
  880  477  516
  226  996  282
  778  531  528
  722  313  162
  975  489  594
  406  312  635
  106  191  147
  180  731   20
  249  869  140
  336  359  426
  266  580  403
  569  702  587
  740  913  549
  197  372  292
  585  964  683
  340  532  249
  592  588  910
  280   78  824
  675  892  101
  642  718  222
  393  359  157
  714  442  999
  851  425  954
  487  545  408
  504  759  191
  509  179  626
  774  859  455
  335  476  523
  573  622  288
  518  561  504
  812  100  602
  433  455  676
  565  453  112
  282  266  523
  642  508  440
  558  512  102
  109  685  128
  291  903  221
  254  370  275
  300  398  431
  341  809  383
  622  948   79
  813  961  308
  972  451  601
  390  877  719
  988  448  275
  184  229  542
  902  307  761
  587  575  909
  442  648  331
  424   98  620
  512  106  578
  411  219  614
  577  294  104
   81  916  468
   84  842  287
   96  261  678
   34  323  226
  943  321   29
  906  619  258
  924  503  215
  929  149  431
   56  505  511
  876  769  999
  994  714  980
  416  495  355
   79  265  420
   37  917  286
   53  782  558
  868  327   59
  926   27  398
  704  348  370
  773  909  356
  969  799  551
  282  138  448
  808   51  437
  417  277  372
  806  291  537
  818  510  460
  945  372   38
  127  191  422
  100  287  753
  341  510  391
  317  252  884
  629  201  567
  164   10  560
  632  205  370
  353  891  990
  609  391   12
  889  564  990
   74  820  241
  356  636  389
  309  232  292
  654  294  199
   45  226  362
  645  308  329
  955  891  186
  180   78  115
  842  938  141
  141  179  159
  401  227  573
  372   73  681
  562  216  682
  184  526  998
  530  450  357
  296  812  233
  398  287  530
  613  539  372
  523  719  554
  377  735  429
  854  319  362
  445  828  221
  506  485  402
  519  603  250
  490  421  819
  638  204  983
  664  585  407
  434  503  124
  512  551  153
  135  449   30
  673   10  513
  682   45  265
   32   44  498
  168  415  698
  151  821  711
  179  682  145
  800  471  326
  376  893  698
  885  523  390
  992   49  159
  949    8   59
   83   47  107
  871   46  660
  610  954  892
  352  956  637
   12  139  444
  517  748  733
  502  731  354
  368  754  687
  197  759  584
  292   25  928
  197  319  514
  359  824   99
  458  827  546
  681  543  197
  160  492  603
  634   82  455
  456   96   53
  399   94  836
  702    2  814
  614  422  467
  161  290  252
  506  605  591
    8  454  407
   46  544  489
   42  491  477
  772  602  767
  359  465  769
  970  360  114
  959  552   83
  945  581  284
   26  314  286
  153  708  707
  444  681  830
  400   65  430
   22  993  185
  327  525  125
  321  665  106
  538  632  959
  552  220  966
   17  787    5
  561  309  865
  997  652  785
  678  924  297
  772  290  460
  322  347  473
  811  393   92
  283  398  625
  349   50  528
  385  403  544
  404  671  204
  430  214  286
  798  480  219
  430  440  811
  240  249  442
  223  510  411
  590   18  592
  468  166  556
  542  165  708
   93   12  480
  893  355  601
  822  348  850
  431  606  256
  367  819  690
  188  247  644
  766  199  514
  384  469  416
  412  520  459
  261  326  646
  746  533   31
  972  788  664
  465  548  470
  257  371  412
  633  703  817
  525   26  466
    6  667  539
  532  692  356
  891  468  602
  709   24  599
  275  449    2
  674  471  289
  683  549   57
  177  917  270
  954  311  715
  991  921  707
  115  946    6
  745  615  446
  646  288  148
  725  333  588
  933  915  326
  828  947  286
  350   59  117
  598   98  286
  436  127   91
  461  223  198
  334  167  679
  506   86  803
  254  237  989
  878  248  371
  416  757  398
  721  841  757
  761  303  973
   24   76  928
  749  280  886
  194  695   42
  134  261  752
  134  557  727
  345  367  861
  380   87  425
  685  424  723
   17  738  451
  902  886  569
  920  272  125
  239  222  797
  361  951  767
  273  835  197
  696  235  427
  247  212  922
  706  389  739
  480  893  290
  877  177  494
  450  864  281
  392  164  313
  799  233  293
  416  168   35
  860  290    4
  989  284  124
  710   88  120
  431  307  526
  515  417  528
  442  400  566
  108  858  371
   47  472  519
  147  627  386
  644  481  315
  168  838  337
  675  409   29
  130  117  449
  959  401  512
  963  416  667
  729  166  375
  843  452  322
  749  325   88
  978  850  511
   91  789  818
  993  552  510
  741  512   45
  836  644  865
  136  851  903
  711  818  984
  933  760  333
  461   66  945
  285  198  321
  726  577  317
  952  421    2
  278  961  835
  995  134  148
  805  999  760
  542  731  575
  657  754  721
  135   43  343
  755  179  318
  372   24  646
  577  194  595
  277    7  440
  530   48  416
  257   54  634
  772  302  492
  789  397   21
  532  270  499
  145  511  583
  600  286  402
  628  449  621
  577  588  199
  485  965  239
  765  760  422
  709  284  676
  962  672  786
  760  716  362
  511  254   53
  626   96  383
  488  316  340
   19  256  733
  680  798  260
  693  578  908
  810  216  783
  485  703  650
  965  741  152
   44  544  334
  880  702  451
  887  581  132
  476   77  741
  661   24  435
  858   68  607
  943  416  836
  936  334  662
    5  397  348
  452  838  182
  801   89  369
  781  853  284
  969   23  717
  482  493  611
  560  483  394
  221  642  492
  641  393  428
  491  752   98
  710  791  437
  615  198  656
  146  646  943
  218  385  132
  934  209  589
  863  299  513
  941  624  167
  648  514  553
  724  157  441
  389  733  241
  236  109  421
  607  816  536
  363  877  317
  508  493  332
  782  929   79
  535  607  463
  877   32  399
  637  626  172
  511  865  972
  560  916  928
  599  325   80
  809  477  224
  724   60  279
  524  454  262
  960  517  994
  216   42  880
  969  487  190
  977  329  652
  916  539  696
  271  581   76
  660   74  681
  768  761  323
  108  821  440
  224  478  560
  373  567  614
  417  716  566
  178  155  529
  994  670  562
  987  621  375
  161  498  922
  527  843  478
  495  975  788
  528   11  567
  713  744  575
  268  746   35
  802   53  869
  789  717  381
  437  703  871
  177  220  104
  638  684   79
  807  535   71
  525  978  321
  576  696  351
  928  572   83
  414  437   25
   75  371  320
  338   89  327
  376   90  239
  363  330  126
   12  260  210
  284   21  356
  403   54  748
  551   49  530
  530  461  249
  640  450  399
  153  754  393
  548  774  958
  602  773  906
  417   11  377
  188  879  740
  486  105  649
  426  929  107
  848  677  563
  913  728  646
  700  116  390
  148  425  782
  564  335  839
  584  652  155
  707  887  518
  489  250  857
  979  726  399
  113  305  420
  402  396  742
  479   99  950
  753  425  677
   88  533  246
  804  138  554
   76  734  294
  472  550  372
  415  621  525
   76  617  903
  821  145  901
  876  539   35
   91  745  637
  871  604  106
  811  466  729
  694  153  573
  100  735  306
  660  640  817
  927   55  814
  852   30  289
  741   33  898
  193   57  636
  260  208  711
  172  215  152
  790  262  520
   92  511  437
  726  622   89
  709  848  318
  269  960  557
  940  814  793
  286   59  993
  529    6  870
  415   58  850
  578   13  524
  261  258  423
  695  247  290
  512  229  270
  485  271  272
  118  461    3
  757  679  808
  830  886  324
  913  315  870
  414  229  764
  386  567  738
   32  657   59
  336  169   14
  821  494  667
  815  606  674
   20  654  529
  482  674   49
  476  321  512
  661  466  229
  869  974  565
  205  686  438
  466  218  494
  567  519  761
  257  658  648
  546  491  467
  102  526  542
  542  949  126
  608  999  976
  867  666  798
  421  801  941
  825  589  335
  871   93  179
  491  670  303
  464  256  249
  318  650  322
  168  807  391
  513    5  179
  770    8  127
  960    9   82
  561  661  885
  176  670  865
  468  382   20
  811  732  457
  709  856  356
  713  378  649
  306  510  409
  963  269  649
  988  749  782
  208  173  181
  679  734  178
  884  870   45
  763  290   80
  228  495  689
  736  653  771
  325  948  972
  985  132  914
  770  859  360
  382  859  755
  781  866  681
  922   20  119
  628  584  547
  584  262  320
   62  407  277
  831  531  304
  979   31  842
  194  538  646
   77   61  758
  245  247  620
  175  298  876
  315  121  893
  185  404  558
  222  359  367
  901  873   23
  109  560  553
  819  848  567
  509  184  809
  188  194   46
  405  255  773
  333  734  547
  283  750  154
  115  220  406
  551  373  358
  851  505  478
  961  847  160
  661  295  417
  489  136  814
  192  307  866
  976  763  437
  255  964   24
  786  900  454
  727  560  520
  814  169  504
  882  573  524
  550  409  236
  567  647  258
  155  576  474
  508  455  921
  718  197    9
  331  356  917
  344   78  748
  204    6  937
  187   83  648
  138   81  913
  314  972  914
  286  971    4
  677  344  702
  326  452  163
  407  131  576
  560  351  137
  701  839  354
  475  503  263
  606  504  651
  919  601  112
  709  224  732
  714  184  103
  261  554  192
  766  381  290
  388  784  853
  447  869  923
  504  124  571
  923  643  251
  323  679  152
  847  477  171
  796  368  649
   80  716  799
  771  677  294
  270  364  957
  253  591  959
   17  756   22
  121  466  617
  401  838  752
  350  604  913
  393  811  828
  646  949  940
  328  230  516
  794  443  695
  136  429  579
  657  140  613
  803  177  821
  829  564  440
  560  469  853
  961  693  979
  382  661   84
  630  180  995
  626  353  575
  616  502  687
  264  223  764
   64  507  569
  575  427  662
  619  807  506
  663  203  959
  978  775  783
  317  749  481
    3  581  875
  320  828  793
  317  838  107
  671  603  282
  524  581  326
  619  728   57
   91  937  198
  182  353  260
  226  759  244
  140  153  149
  387  732  239
  427  761  138
  339  447  421
  278  439  647
   82  135  839
  824  513  865
  117  310  825
  838  670   58
  183   82  130
  212  209  749
  118  151  861
  978  275  262
  273  747  689
  916  739  878
  689  270  339
  358  268  750
  966   97  753
  161  685  813
  174  396  866
   70  861  132
  866  117  790
  737  201  723
  209   85  468
  821  948  557
  182  374  327
  912  671  412
  444  592  746
  567  613  415
  561   75  393
  631  428  740
  976  362  326
  504  171  911
  753  886  430
  738  680  494
  839  371  481
  979  537  330
  333  886  216
  669  357  476
  107  186  484
  302  327   78
  400  231  541
  159  873   75
  744  684   46
  592  363   80
  944  670  496
  811  292  699
  545  959  949
  299  552  632
  683   94   14
  418  603  646
  370  781  758
  364  236  619
  107  837  860
  106  409  344
  492  713   36
  398  460  375
  730  569  497
  733  409  499
  577  349   19
  652  182  824
  768  822  363
  207  862  535
  911  344  372
  868  814  640
   68  792  781
  674  787  205
  182  852  241
  725  665   43
  187  852  838
  615  856  418
  632  277  593
  654  386   27
  805  801  218
  328  416  226
   76  206  209
   81  209  660
   31  231  523
  569  910  110
  815  106  675
  739  830  604
  534  724  869
  379  460  782
  549  270  934
  324  105  218
  841  218  205
  739  259  232
  572  504  356
   66  459  486
  504   66  344
  873  117  119
  261  245  916
  621  157  915
  220  648  409
  630  192  549
  440  773  415
  816  468  543
  475  374  845
  446  219  487
  999  434  835
  304  444  775
  698  203  348
  715  544  424
  206  628  403
  760  782   86
  651  599  486
  973  404  562
  614  229  172
  396  460  782
  434  339  349
   88  790  818
  925  685  952
  922  381  967
  723  870  704
   94  145  400
  308  686  530
  288  716  629
  867  678  982
  554  414  584
  942  429  931
  608  828  977
  599  663  620
  867  330  419
  200  740  588
  225  213  673
  146  675  372
  302  792  589
  299  948  809
   16  942  797
  262  796  418
  591  828  555
  532  403  619
  694  289  960
  801  532  203
  918  746  870
  127  617  829
  350  179  938
  326  510  128
  432  714  226
  948  786  102
  866  664  162
  302  115  584
  714  623  211
  829  582  543
  173  321  260
   47  284  919
  133   35  880
  614   25  827
  768  490  998
  825  502  252
  275  750  219
  716  140  453
  758  864  541
  563  352  768
  197  800  911
  670  540  302
  307  237  726
   76  667  665
  322  617  207
  118  298  820
  283  548  228
  381  502  797
  990  491  579
  250  474  670
  784   55  283
  729  933  464
  255  765  347
  807  818  198
  594  601  446
  374  725  121
  591  760  424
  480  456  809
  974  408  234
  876  153  811
  540  263  238
  535   68  556
   21  293  527
  613   39  765
  761  255  406
  596  279  414
  772  451  527
  258  554  169
  958  697  445
  127    9  107
  607  445  305
  695  435  396
  487  224  873
  671  199  792
  739   37   85
  859  744  284
  947  299  230
  755  817  226
  827  207  658
  882  709  567
  303  509  790
   73  262  270
  917  112   21
  949  277  281
  559  557  918
  668  875  906
  308  669  543
  479  563  879
  311  317  834
  534  751   50
  275  774  278
  200  642  690
  293  196  466
  780  804  135
  866  162  122
  916  783   58
  631  477   70
  878  375   67
  425  621    4
  826  161  926
  147  884  139
  717  936  799
  140  703  405
  284  168   89
  144  738  315
  418  417  564
  439  357  820
   73  113  702
  163  550  647
  144  780  984
   34  592  770
  696  167  452
  666  541  973
  314  622  567
  986   92  636
  301  171    1
  812  146  637
  673  395  895
  583  283  510
  380  482  907
  953  189  148
  513  372  455
  923  505  387
  525   45  877
  630  816  797
  119  776  276
  540  139  396
  560   62  596
  502   97  876
  431  977  533
  867  782  484
  844  409  190
   46   63  700
  102  972  421
  110  987  312
   58  543  365
  657  248   64
  613  658  340
  605  875  408
  746  653  401
  898  980    5
  449  371  108
  496  690   91
  672  657  184
  816   48  744
  121  109  689
  849   88  201
  982  268  418
  569  193  589
  630  267  676
  690  453   47
  496  369  792
  677  412  833
   95  316  802
  957  774  647
  966  842  861
  233  737  194
  260  605  424
  266  274  310
  874  365  762
  411   87  704
  477  356  739
  554  598  454
  107  540   64
  641  631  470
  444  387  133
  277  704  401
  226  869  475
  299  986  127
  831  706   60
  899  442  111
  414  281  804
  579  702  597
  587  807  932
  755  649  537
  844  439  295
  979  235  417
  821  852  719
  546   59  716
  607  889    8
  851  534  334
  926  234   50
  184  710  286
  152  872  638
  132  517  712
   21  970  152
  801  701  104
  438  845   30
  966  454  106
   37  894  741
  276  896  923
  274    6  535
  339  346  129
  141  566  488
  386  418  551
  160   69  822
  586  589  634
  443  633  319
  466  944  856
  704    6  944
  438  937  229
   47  201  738
  283  102  389
  305  168  844
  760  854  880
  827  903  750
  612  138  163
  658   57  491
  622   91  900
  233  144  773
  113   85  645
  399  129  190
  497   49  481
   85  698  906
  604  146  968
  653  767   92
  130  260  706
  288  396  267
  268  625  621
    6  283  805
  992  917  363
  985  716  887
  900  677  593
  892  668  406
   40  259  733
  572  860  510
  154  225  479
  575  750  809
  938  312  243
   36  294  461
  973  150  452
  226  270  159
   66   81  520
  247  346  496
   58  864  207
  395  140  524
  438  901  717
  491  838  807
   85  203  859
  541  931  704
  764   26  272
  912  250  107
  512  278  182
  910   89  345
  242  826   85
  687  889  267
  112  610   93
  445  882  337
  532  746  381
  689  526  854
  696  858  351
  778  798  801
  255    8  362
  200   45   44
  203   50  342
  520  236  135
  228   35  196
  421  236  120
  689  653  418
  692  773  233
  898  438  334
   32  821  511
  419   55   31
  449  776  496
  617  857  815
  691  530  996
  105  959  469
  403  371  317
  309  394  366
  207  449   84
  902  419  633
  361  480  733
  987  318  213
  722  531  649
  600  600   12
  954  968  654
  436  429  111
  169  205  606
  331  227  610
  943  543  304
  146  666  412
  998  544  402
  459  475   58
  269  455   55
  388   98   38
  243  675  858
  172  732  707
  188  120  313
  959  887  640
  719  968  101
  752   83  547
  477  517  337
  908  620  289
  869  878  321
  738   33   20
  817  227  913
  469  260  898
  138  329  593
   23  459  967
  159  339  524
  681  669  674
  216  619  673
  740  360  420
  302  875  950
  539  759  635
  430  548  612
  239  841  169
  323  702  113
  374  615  255
  457  851  958
  721   40  270
  495  842  808
  745  939  343
  484  408  610
  554  739  576
  539  695   49
  535  745  493
  117   88  444
  554  939    3
  665  470  581
  133  876  580
  268  430  703
  436  883  249
  448  823  862
    3  218  505
   85  944  264
   81  994  367
  673  488  484
  506  901  694
  847  914  612
  426  423   29
  971  214  741
  589  221  732
   20  853  541
  995  783  448
  983  854  858
  446  523   27
  418   52  118
   73  566  122
  438   74  361
  354  136  981
  399  183  794
  888  816  366
  863  586  878
  388  254  979
  430  735   19
  922  536   47
  750  686   60
  545  836  683
  828  748  301
  678  297  546
  493  567  351
  514  643  523
   58  191  768
  418  778  387
  273  925  613
  651  160  330
  859  215  624
  750  876   36
  138  836  637
  906  550  568
   46  520  876
  928   79  632
  400  610  906
  380  471   22
  163  624  931
  822  507  661
   49   89  414
  874  593  476
  958  895  660
  910  783  691
  341  147  325
  751  767  297
  194   81  335
  633  808  345
  726  290  602
  550  102  207
  345  194  542
  217   68  103
  290  441  451
  239  464  407
  987  401  195
  300  341  313
  797  409  430
  471  607  441
   82  153  439
  511  578  399
  634  593  414
  630  113  776
  448  679  413
  346  784  577
  320  851  645
  584  584   73
  603  742  196
  165  758  361
  624   23  262
  626   90  435
  943  647  702
  446  598  392
  993  579  904
   41  608  924
  979  209  371
  654  642  136
  776  518  520
  787  369  444
  518  543  529
  824  974  110
  415  582  629
  651  356  869
  903  347  977
  345  269  581
  549  840  613
  433  209  891
  407  630  900
  509   95  409
  510  103  362
  194   69  754"

  puts "total triangles:#{input.split("\n").count}"
  rows = input.split("\n").map{|l|l.split(" ").map{|i|i.strip.to_i}}.transpose
  valid = rows.map{|r|r.each_slice(3).to_a.map{|c|c.sort}}.flatten(1).count{|c|(c[0] + c[1]) > c[2]}
  puts "valid triangles: #{valid}"

#first try, less verbose
  valid = 0
  rows.each do |r|
    combinations = r.each_slice(3).to_a.map{|c|c.sort}
    combinations.each do |combination|
      valid += 1 if (combination[0] + combination[1]) > combination[2]
    end
  end
  puts valid
#puts "valid triangles: #{valid}"