Task

Compute the Information Gain Ratio (IGR) for a categorical feature with k possible values. IGR = IG / H(feature), where IG = H(labels) - sumv (nv/n)H(labels | feature=v) is the standard information gain and H(feature) = -sum_v (n_v/n)log2(n_v/n) is the entropy of the feature's distribution. Return 0.0 if H(feature) = 0. IGR normalises information gain to avoid preferring features with many categories.

Input

• Line 1: n k — total number of samples, number of distinct feature values (1-indexed: 1 to k)
• Lines 2 to n+1: feature_val label — integer feature value and binary label (0 or 1)

Output

Print the Information Gain Ratio as a single float with up to 10 significant digits.

Example

Input:

6 2
1 0
1 1
1 0
2 1
2 1
2 0

Output:

0.08170416595

Scaffolding

Submit a Python file defining:

def ig_ratio(n: int, k: int, feature_vals: list[int], labels: list[int]) -> float:
    ...

Receives the sample count, number of feature categories, a list of feature values, and a list of binary labels; returns the Information Gain Ratio as a float.