package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)


func main() {
	fmt.Println("Advent of Code 2025 - Day 3 - Part 2")
	f,_:= os.Open("3/input")
	defer f.Close()
	scanner := bufio.NewScanner(f)
	var res int64;
	var store_comput [100][13]int64
	for scanner.Scan(){
		bank := scanner.Text()
		init_store_comput(&store_comput)
		max_volt := max_voltage2(bank, 0, 12, &store_comput)
		res += max_volt
	}
	fmt.Println(res)
}

func init_store_comput(store_comput *[100][13]int64){
	for i:= 0; i < 100; i++{
		for j:=0; j < 13; j++{
			store_comput[i][j] = -1
		}
	}
}

var pre = [12]int64{
	1, 10, 100,
	1_000, 10_000, 100_000,
	1_000_000, 10_000_000, 100_000_000,
	1_000_000_000, 10_000_000_000, 100_000_000_000}

func max_voltage2(bank string, i,k int, store_comput *[100][13]int64) int64{
	if (k == 0) {return 0}
	if (i == len(bank)) {return -999999999999999}

	if (store_comput[i][k] != -1){
		return store_comput[i][k]
	}
	
	max1 := max_voltage2(bank, i+1, k, store_comput)

	curr,_ := strconv.Atoi(string(bank[i]))
	max2 := max_voltage2(bank,i+1,k-1,store_comput) + (int64(curr) * pre[k-1])

	store_comput[i][k] = max(max1,max2)
	return store_comput[i][k]
	
}