Introduction

Work is so much more fun when we are part of a team! By combining our different skills, we can be more creative, efficient and productive. And more importantly, when working together we share... not only pizzas, but also knowledge. We can learn from each other, improve our own skills and gain experience.

Teamwork is one of the main ingredients of Hash Code, especially in this challenge!

So, are you up for the challenge?

Summary

You are given a list of contributors, who have already mastered various skills, and a list of projects with different skill requirements. Contributors can improve their skills by completing projects and can mentor each other to work is roles in which they couldn't succeed on their own. Your task is to assign contributors to project roles that fit their qualifications and maximize the score for completed projects.

Problem description

Contributors

There are $$$N$$$ contributors. Each contributor has a name and one or more skills at a specific level $$$(0, 1, 2, ...)$$$. Not possessing a skill is equivalent to possessing a skill at level 0.

Projects

There are $$$ M $$$ projects. Each project is described by:

• its name
• the duration of the project in days (how long it takes to complete a project once it is started)
• the score awarded for completing the project
• the “best before” time in days – if the project last day of work is strictly before the indicated day, it earns the full score. If it’s late (that is, the project is still worked on during or after its "best before day"), it gets one point less for each day it is late, but no less than zero points. See also the example in the "Assignments" section below.
• a list of roles for contributors working on the project

Each project has one or more roles that need to be filled by contributors. Each role requires one skill at a specific level, and can be filled by a single contributor. Each contributor can fill at most one role on a single project.

Filling roles and mentorship

A contributor can be assigned to a project for a specific role (at most one role in a single project), if they either:

• have the skill at the required level or higher; or
• have the skill at exactly one level below the required level, only if another contributor on the same project (assigned to another role), has this skill at the required level or higher. In this case, the contributor will be mentored by their colleague :)

One contributor can mentor multiple people at once, including for the same skill. A contributor can mentor and be mentored by other contributors at the same time.

Not possessing a skill is equivalent to possessing a skill at level 0. So a contributor can work on a project and be assigned to a role with requirement C++ level 1 if they don’t know any C++, provided that somebody else on the team knows C++ at level 1 or higher.

Assignments

Each contributor can start working on day 0 and can be working on at most one project at the same time. Once the work on a project starts, its contributors will be working on it the number of days equal to its duration and then become available to work on other projects.

Learning

Completing a project is a learning opportunity, especially for the contributors working on the edge of their existing abilities! When each project is completed:

• contributors working in roles where the required skill level was equal or higher than their current level improve their skill level by one level
• other contributors keep their skill level

Note that mentoring someone doesn’t increase the level of the skill for the mentor.

Input data sets

File format

Each input data set is provided in a plain text file. The file contains only ASCII characters with lines ending with a single '\n' character (also called “UNIX-style” line endings). When multiple strings and numbers are given in one line, they are separated by a single space between each two elements.

The first line of the data set contains:

• an integer $$$ C $$$ $$$(1 \leq C \leq 10^5)$$$ – the number of contributors,
• an integer $$$ P $$$ $$$(1 \leq P \leq 10^5)$$$ – the number of projects.

This is followed by $$$ C $$$ sections describing individual contributors. Each contributor is described by the following lines:

• the first line contains:
  • the contributor's name (ASCII string of at most 20 characters, all of which are lowercase or uppercase English alphabet letters a-z and A-Z, or numbers 0-9),
  • an integer $$$ N $$$ $$$(1 \leq N \leq 100)$$$ - the number of skills of the contributor.
• the next N lines describe individual skills of the contributor. Each such line contains:
  • the name of the skill (ASCII string of at most 20 characters, all of which are lowercase or uppercase English alphabet letters a-z and A-Z, numbers 0-9, dashes '-' or pluses '+'),
  • an integer $$$ L_i $$$ $$$(1 \leq L_i \leq 10)$$$ - skill level.

This is followed by $$$ P $$$ sections describing individual projects. Each project is described by the following lines:

• the first line contains:
  • the name of the project (ASCII string of at most 20 characters, all of which are lowercase or uppercase English alphabet letters a-z and A-Z or numbers 0-9),
  • an integer $$$ D_i $$$ $$$(1 \leq D_i \leq 10^5)$$$ – the number of days it takes to complete the project,
  • an integer $$$ S_i $$$ $$$(1 \leq S_i \leq 10^5)$$$ – the score awarded for project’s completion,
  • an integer $$$ B_i $$$ $$$(1 \leq B_i \leq 10^5)$$$ – the “best before” day for the project,
  • an integer $$$ R_i $$$ $$$(1 \leq R_i \leq 100)$$$ – the number of roles in the project.
• the next $$$ R_i $$$ lines describe the skills in the project:
  • a string $$$ X_k $$$ – the name of the skill (ASCII string of at most 20 characters, all of which are lowercase or uppercase English alphabet letters a-z and A-Z, numbers 0-9, dashes '-' or pluses '+'),
  • an integer $$$ L_k $$$ $$$(1 \leq L_k \leq 100)$$$ – the required skill level.

Example

Input file

Description

3 3 Anna 1 C++ 2 Bob 2 HTML 5 CSS 5 Maria 1 Python 3 Logging 5 10 5 1 C++ 3 WebServer 7 10 7 2 HTML 3 C++ 2 WebChat 10 20 20 2 Python 3 HTML 3

3 contributors, 3 projects contributor Anna  has C++ skill at level 2 contributor Bob  has HTML skill at level 5  has CSS skill at level 5 contributor Maria  has skill Python at level 3 project Logging needs 1 contributor  that needs to have C++ at level ≥ 3 (2 with mentoring) project WebServer needs 2 contributors  first contributor needs to have HTML at level ≥ 3 (2 with mentoring)  second contributor needs to have C++ at level ≥ 2 (1 with mentoring) project WebChat needs 2 contributors  first contributor needs to have Python at level ≥ 3 (2 with mentoring)  second contributor needs to have HTML at level ≥ 3 (2 with mentoring)

Submissions

The submission file should be a plaintext file containing only ASCII characters.

File format

Your submission describes which projects each contributor is going to work on and in which role.

The first line should contain the integer $$$ E$$$ $$$(0 \leq E \leq P)$$$ – the number of executed projects.

This should be followed by E sections each describing one completed project. Each project should be described by two lines:

• A single line containing the name of the project (as it appears in the input file). Each project can be mentioned at most once in the submission file.
• A single line containing the names of the contributors assigned to each of the project roles, separated by single spaces and listed in the same order as the roles appear in the input file.

Example

Submission file	Description
3 WebServer Bob Anna Logging Anna WebChat Maria Bob	three projects are planned assignments for project WebServer Bob → first role, Anna → second role assignments for project Logging Anna → first role assignments for project WebChat Maria → first role, Bob → second role

Scoring

Each contributor can only work on one project at a time. If one contributor is assigned to multiple projects, the contributor will work on them in the same order as they appear in the submission file. Each project starts immediately on the first day on which all the assigned contributors are available.

If some project assignment is invalid because the assigned contributor does not have the required skill level for the project after finishing all previously assigned projects, the submission is considered invalid and will not be scored.

Each project that is completed successfully receives its assigned score, as defined in the input file, minus penalty points for any delay. If a project is completed after its “best before” time, it gets one point less for each day it is late (but no less than zero points). Note that even if a project scores zero points, the assigned contributors will work on it (and may improve their skills thanks to it).

The total score is the sum of scores for all correctly completed projects.

Note that there are multiple data sets representing separate instances of the problem. The final score for your team will be the sum of your best scores for the individual data sets.