```python
"""The cheapest set of travel passes covering every trip day."""


def _validate_plan(trip_days, passes):
    for day in trip_days:
        if isinstance(day, bool) or not isinstance(day, int) or day < 1:
            raise ValueError("trip days must be positive integers")
    for earlier, later in zip(trip_days, trip_days[1:]):
        if later <= earlier:
            raise ValueError("trip days must be strictly increasing")
    if not passes:
        raise ValueError("at least one pass kind is required")
    for cover in passes:
        span = cover["span"]
        cost = cover["cost"]
        if isinstance(span, bool) or not isinstance(span, int) or span < 1:
            raise ValueError("pass span must be a positive integer")
        if isinstance(cost, bool) or not isinstance(cost, int) or cost < 0:
            raise ValueError("pass cost must be a non-negative integer")


def cheapest_pass_plan(trip_days: list, passes: list) -> dict:
    _validate_plan(trip_days, passes)
    
    if not trip_days:
        return {"total": 0, "purchases": []}
    
    n = len(trip_days)
    # dp[i] is the minimum cost to cover trip_days[i:]
    # We process from the last trip day backwards to the first.
    # State: index i in trip_days (0 to n)
    # Base case: dp[n] = 0 (no trips left to cover)
    
    dp = [0] * (n + 1)
    # best_pass[i] stores the index of the pass kind chosen at trip_days[i]
    # to achieve the optimal cost for covering trip_days[i:]
    best_pass = [-1] * n
    
    for i in range(n - 1, -1, -1):
        current_day = trip_days[i]
        min_cost = float('inf')
        chosen_idx = -1
        
        for k, cover in enumerate(passes):
            span = cover["span"]
            cost = cover["cost"]
            
            # This pass covers days [current_day, current_day + span - 1]
            # We need to find the next trip day that is NOT covered by this pass.
            # A trip day t is covered if current_day <= t < current_day + span.
            # We want the smallest index j > i such that trip_days[j] >= current_day + span.
            
            # Binary search for the first index j >= i+1 where trip_days[j] >= current_day + span
            left = i + 1
            right = n
            while left < right:
                mid = (left + right) // 2
                if trip_days[mid] < current_day + span:
                    left = mid + 1
                else:
                    right = mid
            
            # left is now the index of the first uncovered trip day, or n if all remaining are covered
            next_idx = left
            total_cost = cost + dp[next_idx]
            
            if total_cost < min_cost:
                min_cost = total_cost
                chosen_idx = k
            elif total_cost == min_cost:
                # Tie-breaking: if costs are equal, we don't change the choice based on pass index
                # because the problem says "when several pass kinds tie for a cheapest plan at such a day, 
                # the one listed first is bought". This implies we pick the