import heapq
import sys
from collections import namedtuple
import random

import numpy as np

Job = namedtuple('Job', ['id', 'x1', 'y1', 'x2', 'y2', 's', 'f', 'rew', 'deadline_odjezd'])

BONUS = float('nan')

Kr = 1
Kd = 100
Krand = 100

# 15278973
# 15557121
# 15273737 # rand

# high bonus
# 21478343
# 11601343 - 1, 1, 1
# 11601343 - 1, 1, 1
# 7309176	10, -10, 0



# C
# 15257904
#


class Car:
    def __init__(self, car_id):
        self.id = car_id
        self.time_free = 0
        self.x = 0
        self.y = 0
        self.tasks = []
        self.score = 0

    def add_task(self, task_id):
        self.tasks.append(task_id)

    def __lt__(self, other):
        return self.time_free < other.time_free

    def __str__(self):
        return "CAR {}, time free: {}, x: {}, y: {}, score: {}, tasks: {}".format(self.id, self.time_free, self.x,
                                                                                  self.y,
                                                                                  self.score, str(self.tasks))


def printSol(cars, fn):
    fn = fn.split(".")[-2] + ".out"
    with open(fn, 'w') as f:
        for c in cars:
            # Write ID of car
            f.write(str(len(c.tasks)))
            f.write(" ")

            # Write out all tasks in order that they were appened
            for task in c.tasks:
                f.write(str(task.id))
                f.write(" ")

            # Newline
            f.write("\n")


def distance(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)


def select_task(car, tasks):
    cx, cy = car.x, car.y
    time = car.time_free

    best_cost = -float("inf")
    best_i = -1
    best_bonus = 0
    best_arrival_time = float("nan")
    best_task = None
    for i, task in enumerate(tasks):
        if task:
            if task.deadline_odjezd < time:
                tasks[i] = None
            else:
                dist = distance(cx, cy, task.x1, task.y1)
                arrival = time + dist
                bonus = BONUS if arrival <= task.s else 0
                waiting = max(task.s - arrival, 0)
                cost = Kr*task.rew - Kd*dist + bonus - waiting + random.random()*Krand
                # print task.rew, dist, bonus, waiting
                if cost > best_cost:
                    best_task = task
                    best_bonus = bonus
                    best_cost = cost
                    best_i = i
                    best_arrival_time = time + dist + waiting + task.rew

    if not best_task:
        return -1
    car.x, car.y = best_task.x2, best_task.y2
    car.time_free = best_arrival_time
    car.score += best_task.rew + best_bonus
    car.add_task(best_task)
    return best_i


def print_cars(cars):
    print("\n".join(list(map(str, cars))))


def solve(input_path):
    global BONUS
    f = open(input_path, "r")
    head = f.readline()
    R, C, F, N, B, T = map(int, head.split())
    # print("Row {}, col {}, cars {}, tasks {}, bonus {}, end time {}".format(R, C, F, N, B, T))
    BONUS = int(B)

    cars = []

    for i in range(F):
        cars.append(Car(i + 1))

    tasks = []
    for i, job in enumerate(f):
        h = [i]
        h.extend(map(int, job.split()))
        hh = h.copy()
        h.append(0)
        h.append(0)
        j = Job(*h)
        rew = abs(j.x1 - j.x2) + abs(j.y1 - j.y2)
        hh.append(rew)
        hh.append(j.f - rew)
        j = Job(*hh)
        tasks.append(j)

    # print(R, C, F, N, B, T)
    # print(tasks)

    heapq.heapify(cars)

    while True:
        # print("##next it##")
        # print_cars(cars)
        car = heapq.heappop(cars)
        # print("selected car", car.id)

        task_pos = select_task(car, tasks)
        heapq.heappush(cars, car)

        if task_pos < 0:
            break
        tasks[task_pos] = None

        if car.time_free > T:
            break

    cars = sorted(cars, key=lambda x: x.id)

    # print_cars(cars)

    return cars


def eval(filename, N):
    scores = []
    best_score = -1
    best_carlist = []

    for i in range(N):
        print("%d/ %d" % (i, N))
        # Get solution
        carlist = solve(filename)

        # Evaluate solution
        score = 0
        for c in carlist:
            score += c.score

        # Append to score list for statistics
        scores.append(score)

        # Update best score and carlist
        if score > best_score:
            best_score = score
            best_carlist = carlist

    # Print out statistics
    scores = np.array(scores)
    print("Results --- min: {}, max: {}, mean: {}, std: {}".format(np.min(scores), np.max(scores), np.mean(scores),
                                                                   np.std(scores)))

    # Write solution to file for submission
    printSol(best_carlist, filename)


if __name__ == "__main__":
    eval(sys.argv[1], 1)