import random
import numpy as np
from typing import List
class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
CROSSOVER_RATE = 0.53
MUTATION_RATE = 0.013
REPLACE_RATE = 0.15
items=[]
class Individual:
    def __init__(self, bits: List[int]):

        self.bits = bits
    
    def __str__(self):
        return repr(self.bits)

    def __hash__(self):
        return hash(str(self.bits))
    
    def fitness(self) -> float:
        total_value = sum([
            bit * item.value
            for item, bit in zip(items, self.bits)
        ])

        total_weight = sum([
            bit * item.weight
            for item, bit in zip(items, self.bits)
        ])

        if total_weight <= CAPACITY:
            return total_value
        
        return 0





def generate_initial_population(count=6) -> List[Individual]:
    population = set()

    # generate initial population having `count` individuals
    while len(population) != count:
        # pick random bits one for each item and 
        # create an individual 
        bits = [
            random.choice([0, 1])
            for _ in items
        ]
        population.add(Individual(bits))

    return list(population)


def selection(population: List[Individual]) -> List[Individual]:
    props=[]
    parents = []
    total_fit=0
    for i in range (len(population)):
        total_fit=total_fit+population[i].fitness()
    for i in range(len(population)):
        fitpr=population[i]/total_fit
        props.append(fitpr)
        proparr = np.array(props)
    count=0
    while count!=(len(population)//2):
        parent1=np.random.choice(population,p=proparr,replace=False)
        parent2=np.random.choice(population,p=proparr,replace=False)
        if[parent1,parent2]not in parents:
            parents.append([parent1,parent2])
            count=count+1
    
    return parents


def crossover(parents: List[Individual]) -> List[Individual]:
    r=random.randint(1,number_of_items)
    child1=parents[0].bits[:r]+parents[1].bits[r:]
    child2=parents[0].bits[r:]+parents[1].bits[:r]
    return [Individual(child1), Individual(child2)]


def mutate(individuals: List[Individual]) -> List[Individual]:
    r=random.randint(1,number_of_items)
    if r<MUTATION_RATE:
        individuals.bits[r]=~individuals.bits[r]
       


def next_generation(population: List[Individual]) -> List[Individual]:
    next_gen = []
    while len(next_gen) < len(population):
        children = []

        # we run selection and get parents
        parents = selection(population)

        # reproduction
        if random.random() < REPLACE_RATE:
            children = parents
        else:
            # crossover
            if random.random() < CROSSOVER_RATE:
                children = crossover(parents)
            
            # mutation
            if random.random() < MUTATION_RATE:
                mutate(children)

        next_gen.extend(children)

    return next_gen[:len(population)]


def print_generation(population: List[Individual]):
    for individual in population:
        print(individual.bits, individual.fitness())
    print()
    print("Average fitness", sum([x.fitness() for x in population])/len(population))
    print("-" * 32)


def average_fitness(population: List[Individual]) -> float:
    return sum([i.fitness() for i in population]) / len(population)


def solve_knapsack() -> Individual:
    population = generate_initial_population()

    avg_fitnesses = []

    for _ in range(200):
        avg_fitnesses.append(average_fitness(population))
        population = next_generation(population)

    population = sorted(population, key=lambda i: i.fitness(), reverse=True)
    return population[0]


if __name__ == '__main__':
    TEST_CASE=int(input('enter number of test cases'))
    for i in range(TEST_CASE):
       number_of_items=int(input('enter number of items'))
       CAPACITY = int(input('enter the capacity'))
       for i in range(number_of_items) :
          x,y=map(int, input().split())
          items.append(Item(x,y))
       solution = solve_knapsack()
       print(solution, solution.fitness())