import random, itertools, numpy, math, copy
from operator import itemgetter

H = 0.8


def count_deadline(tasks):
    deadline = 0
    for task in tasks:
        deadline += task[2] * H
    return int(deadline)


def count_sum(tasks):
    sum = 0
    for task in tasks:
        sum += task[2]
    return sum


def calculate_score(p, deadline):
    time = 0
    score = 0
    for task in p:
        time += task[2]
        if time < deadline:
            score += (deadline - time) * task[0]
        else:
            score += (time - deadline) * task[1]
    return score


def brute_force(tasks):
    global MINI
    mini = MINI
    perm = list(itertools.permutations(tasks))
    deadline = count_deadline(tasks)
    for p in perm:
        score = calculate_score(p, deadline)
        if score < mini:
            mini = score
            line = (p, deadline, score)
    return line



def order_tasks(tasks, n):
    ordered_tasks = sorted(tasks, key=lambda task: 1.0 * task[2] / task[n])
    return ordered_tasks

def find_place(task_to_insert, tasks_after):
    for i in range(len(tasks_after)):
        if tasks_after[i][2] / tasks_after[i][1] <= task_to_insert[2]/task_to_insert[1]:
            return i
    return len(tasks_after)

def compute_result(tasks_before, tasks_after):
    return 10

def get_best_candidate(tasks_before, tasks_after):
    maxi = -111111111
    best_option = None
    for task in tasks_before:
        j = find_place(task, tasks_after)
        i = tasks_before.index(task)
        result = compute_result(tasks_before, tasks_after, i, j)
        if result > maxi:
            maxi = result
            best_option = (task, i ,j)
    if result < 0:
        return None
    return best_option

def own_algorithm(tasks):
    score = 10000000000
    # for i in range(10):
    tasks = order_tasks(tasks,0)
    tasks_before = tasks
    tasks_after = []

    best_option = get_best_candidate(tasks_before)[0]
    while best_option is not None:
        tasks_after.insert(best_option[0],best_option[1])
        tasks_before.remove(best_option[0])
    tasks = tasks_before+tasks_after

    return calculate_score(tasks, count_deadline(tasks))




# n=10
# results = [1936, 1042, 1586, 2139, 1187, 1521, 2170, 1720, 1574, 1869]   #0.2 1.75 6.8 16.12 11
# results = [1025, 615, 917, 1230, 630, 908, 1374, 1020, 876, 1136]    #0.4  1.02 10.34
# results = [841, 615, 793, 815, 521, 755, 1101, 610, 582, 710]   #0.6 8.3
# results = [818, 615, 793, 803, 521, 755, 1083, 540, 554, 671]   #0.8 36.6

# n=200
# results = [526666, 566643, 529919, 603709, 547953, 502276, 479651, 530896, 575353, 572866] #-3.7
# results = [301499, 355714, 308278, 360852, 322268, 292453, 279576, 288746, 331107,332808] #-3.5
# results = [254268, 266028, 254647, 297269, 260455, 236160, 247555, 225572, 255029, 269236] # 3.19 #2.61
# results = [254268, 266028, 254647, 297269, 260455, 236160, 247555, 225572, 255029, 269236] #43.4 46.5
# n=1000
# results = [15190371, 13356727, 12919259,12705290,13276868,12236080,14160773,13314723,12433821,13395234]
# results = [8570154,7592040,7313736,7300217,7738367,7144491,8426024,7508507,7299271,7617658]
# results = [6411581, 6112598, 5985538, 6096729, 6348242, 6082142, 6575879, 6069658, 6188416, 6147295]
# results = [6411581, 6112598, 5985538, 6096729, 6348242, 6082142, 6575879, 6069658, 6188416, 6147295]


data = open('inputs_sprawko.txt', 'r').readlines()
result = 0
for line in data:
    line = line.split('\t')
    n = int(line[0])
    k = int(line[1])
    H = float(line[2])
    score = int(line[3])
    file_dt = 'tests' + str(n) + '.txt'
    file_dt = open(file_dt, 'r').readlines()
    li = []
    for i in range(1 + (k - 1) * (n + 1) + 1, 1 + k * (n + 1)):
        line = file_dt[i]
        # print(line)
        task = ''.join(line)
        task = task.split(' ')
        task = (int(task[1]), int(task[2]), int(task[0]))
        # print('Line ', i-(1+(k-1)*(n+1)+1), ': ', task[1], task[2], task[0])
        li.append(task)
    tasks = tuple(li)
    print('Test ', n, ' ', k, ' ', 100 * (own_algorithm(tasks) - score) / score, own_algorithm(tasks), score)
    result += 100 * (own_algorithm(tasks) - score) / score
print('Result: ', result / 28.0)

# tasks = generate_tasks()
# tasks = ((6, 15, 7), (10, 12, 5), (9, 13, 4), (9, 12, 8), (5, 2, 2), (5, 4, 9), (3, 1, 4))
# print(type(tasks))
# print(brute_force(tasks))
# print(own_algorithm(tasks))