public class Main {
    public static void main(String[] args) {
        final int[] weights = {1, 1, 1, 5, 13, 3}, costs = {1, 1, 1, 5, 10, 12};
        final int minWeight = 15;
        int maxWeight = 0;
        for(final int weight: weights){
            maxWeight += weight;
        }
        final int[] minCost = new int[maxWeight + 1];
        for(int i = 1; i <= maxWeight; i++){
            minCost[i] = Integer.MAX_VALUE;
        }
        for(int i = 0; i < weights.length; i++){
            for(int j = maxWeight; j >= weights[i]; j--){
                if(minCost[j - weights[i]] != Integer.MAX_VALUE){
                    minCost[j] = Math.min(minCost[j], minCost[j - weights[i]] + costs[i]);
                }
            }
        }
        int answer = Integer.MAX_VALUE;
        for(int i = minWeight; i <= maxWeight; i++){
            answer = Math.min(answer, minCost[i]);
        }
        System.out.println(answer);
    }
}

cHVibGljIGNsYXNzIE1haW4gewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGZpbmFsIGludFtdIHdlaWdodHMgPSB7MSwgMSwgMSwgNSwgMTMsIDN9LCBjb3N0cyA9IHsxLCAxLCAxLCA1LCAxMCwgMTJ9OwogICAgICAgIGZpbmFsIGludCBtaW5XZWlnaHQgPSAxNTsKICAgICAgICBpbnQgbWF4V2VpZ2h0ID0gMDsKICAgICAgICBmb3IoZmluYWwgaW50IHdlaWdodDogd2VpZ2h0cyl7CiAgICAgICAgICAgIG1heFdlaWdodCArPSB3ZWlnaHQ7CiAgICAgICAgfQogICAgICAgIGZpbmFsIGludFtdIG1pbkNvc3QgPSBuZXcgaW50W21heFdlaWdodCArIDFdOwogICAgICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbWF4V2VpZ2h0OyBpKyspewogICAgICAgICAgICBtaW5Db3N0W2ldID0gSW50ZWdlci5NQVhfVkFMVUU7CiAgICAgICAgfQogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCB3ZWlnaHRzLmxlbmd0aDsgaSsrKXsKICAgICAgICAgICAgZm9yKGludCBqID0gbWF4V2VpZ2h0OyBqID49IHdlaWdodHNbaV07IGotLSl7CiAgICAgICAgICAgICAgICBpZihtaW5Db3N0W2ogLSB3ZWlnaHRzW2ldXSAhPSBJbnRlZ2VyLk1BWF9WQUxVRSl7CiAgICAgICAgICAgICAgICAgICAgbWluQ29zdFtqXSA9IE1hdGgubWluKG1pbkNvc3Rbal0sIG1pbkNvc3RbaiAtIHdlaWdodHNbaV1dICsgY29zdHNbaV0pOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGludCBhbnN3ZXIgPSBJbnRlZ2VyLk1BWF9WQUxVRTsKICAgICAgICBmb3IoaW50IGkgPSBtaW5XZWlnaHQ7IGkgPD0gbWF4V2VpZ2h0OyBpKyspewogICAgICAgICAgICBhbnN3ZXIgPSBNYXRoLm1pbihhbnN3ZXIsIG1pbkNvc3RbaV0pOwogICAgICAgIH0KICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oYW5zd2VyKTsKICAgIH0KfQ==