4 3 10 1000 1 2 1000 3 1000 1 5000 1 2 3 4 50000 3 50000 4 50000 3 4 50000 1 50000 1 50000 2 50000 1 50000 2 50000 1 8 4 20 1000 1 1000 2 1000 3 1000 2 10000 1 20000 2 40000 3 4 50000 1 2 50000 1 4 50000 1 50000 1 3 4 50000 1 2 3 4 50000 1 3 4 50000 1 2 3 4 50000 1 3 4 50000 1 5 7 3 4 50000 1 2 3 4 50000 1 2 3 4 50000 1 2 3 4 50000 1 6 8 50000 1 5 3 4 50000 1 2 3 4 50000 1 2 3 4 50000 1 2 3 4 5 6 7 8 2 2 5 10000 1 20000 2 30000 1 2 40000 1 2 10000 1 10000 2 5000 1 2 0 0 0