9

1 2 10

2 2 100

3 2 300

4 25 900

5 2 200

6 3 100

7 4 100

8 5 100

9 10 100