from collections import Counter
from functools import cache

def part1(containers: list[int]) -> int:
    @cache
    def combinations(index: int, remaining: int) -> int:
        if index == len(containers):
            return 1 if remaining == 0 else 0
        return combinations(index + 1, remaining) + combinations(index + 1, remaining - containers[index])
    return combinations(0, 150)

def part2(containers: list[int]) -> int:
    @cache
    def min_used(index: int, remaining: int, used: int) -> int | float:
        if index == len(containers):
            return used if remaining == 0 else float('inf')
        return min(min_used(index + 1, remaining, used), min_used(index + 1, remaining - containers[index], used + 1))
    min_used = min_used(0, 150, 0)
    @cache
    def count_min(index: int, remaining: int, used: int) -> int | float:
        if index == len(containers):
            return 1 if (remaining == 0 and used == min_used) else 0
        return count_min(index + 1, remaining, used) + count_min(index + 1, remaining - containers[index], used + 1)
    return count_min(0, 150, 0)

if __name__ == '__main__':
    with open('input') as f:
        containers = list(sorted((int(line.strip()) for line in f), reverse=True))
    print(part1(containers))
    print(part2(containers))