Bargers at the Board Game Cafe

Struggling to find employment, some of the Board Games members have decided to open a board game cafe! On the first day, everything seems to be going swell until the store reaches full capacity. Thankfully, you've planned for this by buying exactly enough board games as there are tables, so every table can get one game.

Unfortunately, this careful planning didn't account for the fact that everyone wants to play Avalon! All the patrons are queuing for Avalon, but bargers are running rampant, and some people never get to play. To solve this, they decide to instead to split up the games so everyone gets exactly one game at random.

To do this, they have invested in some new high-tech conveyer splitter technology. They will place all the games on one conveyer line, and use splitters that will evenly distrubte the items along output belts, while also making sure the games are random.

For example, if we have 4 board games to split, we can split our games like so, using a total of 3 splitters. (We can treat each number with a vertical line below a point of a splitter.)

4
├── 2
│   ├── 1
│   └── 1
└── 2
    ├── 1
    └── 1

However, it isn't that simple, each of the members has already begun planning franchises of this board game cafe, and each one has invested in varying models of splitter technology. This is indicated by your input. Your input contains lines that consists of 2 numbers each, for example:

4 2
4 4
8 3
6 3
18 5
125 6

The first number indicates the number of board games a store wants to split. The second number indicates the model number of the splitter.

The model number indicates the maximum number of ways the splitter can split a belt. For example, a splitter with model number 4 is able to split a belt either 2, 3, or 4 ways evenly. Each store has made sure that the games are evenly divisible using the model availible (no fractional board games.)

They have hired you as an (unpaid) intern to help them minimize their splitter costs. For each store your goal is to find the fewest number of splitters required to evenly disitrubute all the games to each table.

For example:

• For 4 2, we can split our games as shown in the diagram above. This requires 3 splitters.
  • Split 1 line of 4, into 2 lines of 2. (split by 2)
  • Then, split 2 lines of 2, into 4 lines of 1. (split by 2)
• For 4 4 we could do the same solution as 4 2, but it would be cheaper to use our upgraded model. This requires 1 splitter.
• For 8 3 we cannot use our upgraded splitter to its fullest potenial. This requires 7 splitters.
  • Split 1 line of 8, into 2 lines of 4. (split by 2)
  • Split 2 lines of 4, into 4 lines of 2. (split by 2)
  • Split 4 lines of 2, into 8 lines of 1. (split by 2)
• Split 1 line of 4, into 4 lines of 1. (split by 4)
• For 6 3, this requires 3 splitters.
  • Split 1 line of 6, into 2 lines of 3. (split by 2)
  • Split 2 lines of 3, into 6 lines of 1. (split by 3)
• For 18 5, this requires 9 splitters.
• For 125 6, this requires 31 splitters.

In total, for all of these board game cafes, we need 3 + 1 + 7 + 3 + 9 + 31 = 54 splitters. For your full input, what is the total number of splitters needed?