Optimized Ship Boarding

After adhering to local customs, you arrive just in time for the ship’s departure – only to discover that many passengers are bound for Lübeck! Not wanting to be late for the awards ceremony (and needing extra time to store your stolen artworks), you decide to speed up the boarding process.

The ship has a row of \( n \) seats, all reserved by \( n \) passengers. Each passenger holds a ticket that indicates their designated seat as well as one of \( g \) boarding groups.

During boarding, one entire group is called at a time. Within each group the boarding order is uniformly random (i.e. every possible order is equally likely). Each passenger may choose to board from the front (before seat 1) or from the back (after seat \( n \)), and will proceed to their designated seat before the next passenger boards.

The inconvenience arises when a boarding passenger has to pass by someone already seated – this is counted as one "pass". Formally, if for a given boarding order within a group the probability that a passenger passes exactly \( k \) seated passengers is \( p_k \), then the expected cost for that passenger is \[ \sum_{k\ge1} k\cdot p_k. \] With full control over the order in which the groups board, and by choosing for each passenger the optimal door (front or back), your goal is to minimize the overall expected number of passes incurred during boarding. Output this minimal expected value.

inputFormat

The first line contains two integers \( n \) and \( g \): the total number of seats (and passengers) and the number of boarding groups. Each of the next \( n \) lines contains two integers: the designated seat number (from 1 to \( n \)) and the group identifier (an integer between 1 and \( g \)).

outputFormat

Output a single number representing the minimal expected number of times a passenger must pass by an already seated passenger. It is guaranteed that the answer computed by an optimal strategy (choosing both the boarding group order and the door for each passenger) can pass all test cases.

sample

5 2
1 1
2 1
3 1
4 2
5 2

1.0