package main

import (
    "fmt"
    "math"
    "sort"
)

func main() {
    programs := [][]int{{0, 1, 3}, {0, 1, 4}}
    nums := 1
    ret := minCost(programs, nums)
    fmt.Println(ret)
}

// 每一个项目都有三个数，[a,b,c]表示这个项目a和b乐队参演，花费为c
// 每一个乐队可能在多个项目里都出现了，但是只能挑一次
// nums是可以挑选的项目数量，所以一定会有nums*2只乐队被挑选出来
// 乐队的全部数量一定是nums*2，且标号一定是0 ~ nums*2-1
// 返回一共挑nums轮(也就意味着一定请到所有的乐队)，最少花费是多少？
func minCost(programs [][]int, nums int) int {
    if nums == 0 || len(programs) == 0 {
        return 0
    }
    size := clean(programs)
    map1 := init0(1 << (nums << 1))
    var map2 []int
    if (nums & 1) == 0 {
        // nums = 8 , 4
        f(programs, size, 0, 0, 0, nums>>1, &map1)
        map2 = map1
    } else {
        // nums == 7 4 -> map1 3 -> map2
        f(programs, size, 0, 0, 0, nums>>1, &map1)
        map2 = init0(1 << (nums << 1))
        f(programs, size, 0, 0, 0, nums-(nums>>1), &map2)
    }
    // 16 mask : 0..00 1111.1111(16个)
    // 12 mask : 0..00 1111.1111(12个)
    mask := (1 << (nums << 1)) - 1
    ans := math.MaxInt64
    for i := 0; i < len(map1); i++ {
        if map1[i] != math.MaxInt64 && map2[mask&(^i)] != math.MaxInt64 {
            ans = getMin(ans, map1[i]+map2[mask&(^i)])
        }
    }
    return twoSelectOne(ans == math.MaxInt64, -1, ans)
}

func getMin(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}
func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func twoSelectOne(c bool, a int, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

// [
// [9, 1, 100]
// [2, 9 , 50]
// ...
// ]
func clean(programs [][]int) int {
    x := 0
    y := 0
    for _, p := range programs {
        x = getMin(p[0], p[1])
        y = getMax(p[0], p[1])
        p[0] = x
        p[1] = y
    }
    //Arrays.sort(programs, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (a[1] != b[1] ? (a[1] - b[1]) : (a[2] - b[2])));
    sort.Slice(programs, func(i, j int) bool {
        //a := programs[i]
        //b := programs[j]
        if programs[i][0] != programs[j][0] {
            return programs[i][0] > programs[j][0]
        } else {
            if programs[i][1] != programs[j][1] {
                return programs[i][1] > programs[j][1]
            } else {
                return programs[i][2] > programs[j][2]
            }
        }
    })
    x = programs[0][0]
    y = programs[0][1]
    n := len(programs)
    // (0, 1, ? )
    for i := 1; i < n; i++ {
        if programs[i][0] == x && programs[i][1] == y {
            programs[i] = nil
        } else {
            x = programs[i][0]
            y = programs[i][1]
        }
    }
    size := 1
    for i := 1; i < n; i++ {
        if programs[i] != nil {
            programs[size] = programs[i]
            size++
        }
    }
    // programs[0...size-1]
    return size
}

func init0(size int) []int {
    arr := make([]int, size)
    for i := 0; i < size; i++ {
        arr[i] = math.MaxInt64
    }
    return arr
}

func f(programs [][]int, size int, index int, status int, cost int, rest int, map0 *[]int) {
    if rest == 0 {
        (*map0)[status] = getMin((*map0)[status], cost)
    } else {
        if index != size {
            f(programs, size, index+1, status, cost, rest, map0)
            pick := 0 | (1 << programs[index][0]) | (1 << programs[index][1])
            if (pick & status) == 0 {
                f(programs, size, index+1, status|pick, cost+programs[index][2], rest-1, map0)
            }
        }
    }
}