> input:
> 19
> 6
> 7
> 1 2 2 2
> 1 3 2 2
> 1 4 2 2
> 2 5 5 10
> 4 5 7 7
> 3 5 10 5
> 5 6 5 10
> ouput:
> 14
> 
> input:
> 15
> 12
> 16
> 1 8 20 0
> 1 2 10 0
> 2 8 5 0
> 1 7 100 0
> 2 3 5 1
> 3 4 5 1
> 4 5 5 1
> 5 6 5 1
> 6 12 5 1
> 8 12 10 20
> 8 9 1 1
> 9 10 1 1
> 10 11 1 1
> 11 7 2 10
> 7 12 10 1
> 11 4 1 0
> output:
> 30
> 
> input:
> 250
> 21
> 244
> 1 2 99 0
> 1 3 17 0
> 1 4 81 0
> 1 5 46 0
> 1 6 79 0
> 1 8 97 0
> 1 10 68 0
> 1 14 17 0
> 1 18 87 0
> 2 1 41 0
> 2 3 10 0
> 2 4 1 0
> 2 5 40 0
> 2 6 35 0
> 2 7 4 0
> 2 8 35 0
> 2 9 89 0
> 2 10 36 0
> 2 14 61 0
> 2 15 53 0
> 2 20 23 0
> 3 1 8 0
> 3 2 81 0
> 3 4 40 0
> 3 5 89 0
> 3 6 3 0
> 3 7 10 0
> 3 8 93 0
> 3 9 99 0
> 3 10 69 0
> 3 12 50 0
> 3 17 83 0
> 4 1 96 0
> 4 2 37 0
> 4 3 32 0
> 4 5 59 0
> 4 6 54 0
> 4 7 70 0
> 4 9 19 0
> 4 14 56 0
> 4 17 95 0
> 4 20 62 0
> 5 1 93 0
> 5 2 63 0
> 5 3 32 0
> 5 4 68 0
> 5 6 22 0
> 5 7 32 0
> 5 8 96 0
> 5 10 9 0
> 5 11 64 0
> 5 12 42 0
> 5 13 23 0
> 5 14 96 0
> 5 15 51 0
> 6 2 77 0
> 6 3 56 0
> 6 4 31 0
> 6 5 40 0
> 6 7 61 0
> 6 8 67 0
> 6 9 24 0
> 6 10 18 0
> 6 11 6 0
> 6 14 68 0
> 7 2 86 0
> 7 4 22 0
> 7 5 50 0
> 7 6 93 0
> 7 8 66 0
> 7 9 2 0
> 7 10 80 0
> 7 11 70 0
> 7 12 80 0
> 7 13 50 0
> 7 14 57 0
> 7 15 17 0
> 7 16 78 0
> 7 17 35 0
> 7 20 19 0
> 8 1 72 0
> 8 3 49 0
> 8 4 32 0
> 8 5 8 0
> 8 6 3 0
> 8 7 23 0
> 8 9 32 0
> 8 10 54 0
> 8 11 34 0
> 8 12 85 0
> 8 15 9 0
> 8 16 38 0
> 9 2 28 0
> 9 6 8 0
> 9 7 51 0
> 9 8 72 0
> 9 10 92 0
> 9 11 14 0
> 9 12 73 0
> 9 13 74 0
> 9 15 96 0
> 9 17 43 0
> 9 18 32 0
> 9 19 34 0
> 9 20 33 0
> 10 2 41 0
> 10 3 1 0
> 10 5 66 0
> 10 7 34 0
> 10 8 35 0
> 10 9 49 0
> 10 11 91 0
> 10 12 82 0
> 10 13 10 0
> 10 14 88 0
> 10 15 68 0
> 10 16 34 0
> 10 17 73 0
> 10 19 82 0
> 11 2 6 0
> 11 5 41 0
> 11 6 94 0
> 11 7 24 0
> 11 8 6 0
> 11 9 12 0
> 11 10 9 0
> 11 12 93 0
> 11 13 5 0
> 11 14 32 0
> 11 15 36 0
> 11 16 80 0
> 11 19 79 0
> 11 20 90 0
> 12 3 31 0
> 12 5 45 0
> 12 6 79 0
> 12 7 64 0
> 12 8 66 0
> 12 9 57 0
> 12 10 59 0
> 12 11 68 0
> 12 13 5 0
> 12 14 76 0
> 12 15 21 0
> 12 16 76 0
> 12 17 83 0
> 12 18 54 0
> 13 2 96 0
> 13 4 15 0
> 13 5 60 0
> 13 6 98 0
> 13 7 91 0
> 13 8 50 0
> 13 10 17 0
> 13 11 8 0
> 13 12 81 0
> 13 14 43 0
> 13 15 79 0
> 13 16 13 0
> 13 17 72 0
> 13 18 83 0
> 13 20 60 0
> 14 3 25 0
> 14 5 91 0
> 14 6 57 0
> 14 8 6 0
> 14 10 88 0
> 14 11 98 0
> 14 12 65 0
> 14 13 43 0
> 14 15 47 0
> 14 16 64 0
> 14 17 79 0
> 14 18 55 0
> 14 19 31 0
> 14 20 87 0
> 15 5 85 0
> 15 7 98 0
> 15 9 53 0
> 15 11 98 0
> 15 12 98 0
> 15 13 38 0
> 15 14 77 0
> 15 16 84 0
> 15 17 31 0
> 15 18 24 0
> 15 19 54 0
> 15 20 53 0
> 16 6 86 0
> 16 8 76 0
> 16 9 74 0
> 16 10 83 0
> 16 11 78 0
> 16 12 51 0
> 16 13 11 0
> 16 14 5 0
> 16 15 86 0
> 16 17 5 0
> 16 18 55 0
> 16 19 27 0
> 16 20 27 0
> 17 2 25 0
> 17 6 39 0
> 17 9 43 0
> 17 11 16 0
> 17 12 57 0
> 17 13 97 0
> 17 14 56 0
> 17 15 98 0
> 17 16 1 0
> 17 18 77 0
> 17 19 16 0
> 17 20 58 0
> 18 2 96 0
> 18 5 24 0
> 18 8 85 0
> 18 14 60 0
> 18 15 42 0
> 18 16 90 0
> 18 17 87 0
> 18 19 61 0
> 18 20 83 0
> 19 4 77 0
> 19 5 10 0
> 19 10 15 0
> 19 12 71 0
> 19 13 75 0
> 19 14 36 0
> 19 15 23 0
> 19 16 14 0
> 19 17 87 0
> 19 18 40 0
> 19 20 7 0
> 20 4 61 0
> 20 9 19 0
> 20 11 92 0
> 20 12 84 0
> 20 13 87 0
> 20 15 31 0
> 20 16 93 0
> 20 17 59 0
> 20 18 42 0
> 20 19 52 0
> 20 21 10 10
> 
> output:
> 56