Задача B. Школа олимпийского резерва ≡

Автор:Жюри ROI-2011   Ограничение времени:2 сек
Входной файл:school.in   Ограничение памяти:256 Мб
Выходной файл:school.out  
Максимальный балл:100  

Условие

Внимание! Используется лишь часть тестов из оригинального набора!

Для подготовки к чемпионату мира по футболу 2018 года создается школа олимпийского резерва. В нее нужно зачислить M юношей 1994-1996 годов рождения. По результатам тестирования каждому из N претендентов был выставлен определенный балл, характеризующий его мастерство. Все претенденты набрали различные баллы. В составе школы олимпийского резерва хотелось бы иметь A учащихся 1994 г.р., B – 1995 г.р. и C – 1996 г.р. (A + B + C = M). При этом минимальный балл зачисленного юноши 1994 г.р. должен быть больше, чем минимальный балл зачисленного 1995 г.р., а минимальный балл зачисленного 1995 г.р. должен быть больше, чем минимальный балл зачисленного 1996 г.р. Все претенденты, набравшие балл больше минимального балла для юношей своего года рождения, также должны быть зачислены.

В базе данных для каждого претендента записаны год его рождения и тестовый балл. Требуется определить, сколько нужно зачислить юношей каждого года рождения M94, M95 и M96 (M94 + M95 + M96 = M), чтобы значение величины F = |M94 − A| + |M95 − B| + |M96 − C| было минимально, все правила, касающиеся минимальных баллов зачисленных, были соблюдены, и должен быть зачислен хотя бы один юноша каждого требуемого года рождения.

В первом примере на первом наборе ответ не существует, потому что нельзя пригласить хотя бы одного юношу 1995 г.р. Во втором наборе ответ существует и единственный, в третьем – нельзя выполнить правило относительно минимальных баллов.

Во втором примере правильным является также ответ 2 2 2 2.

Подзадача 1 (25 баллов): K = 1; N ≤ 100; каждый претендент характеризуется своим баллом от 1 до N.

Подзадача 2 (25 баллов): Сумма значений N по всем тестовым наборам не превосходит 10 000, каждый претендент характеризуется своим баллом от 1 до 109.

Подзадача 3 (25 баллов): Сумма значений N по всем тестовым наборам не превосходит 100 000, каждый претендент характеризуется своим баллом от 1 до N.

Подзадача 4 (25 баллов): Сумма значений N по всем тестовым наборам не превосходит 300 000, каждый претендент характеризуется своим баллом в диапазоне от 1 до 109.

Формат входного файла

В первой строке входного файла находится число K – количество наборов входных данных. Далее следуют описания каждого из наборов. В начале каждого набора расположены три натуральных числа A, B, C. Во второй строке описания находится число N – количество претендентов (гарантируется, что N ≥ A + B + C). В каждой из следующих N строк набора содержатся два натуральных числа – год рождения (число 1994, 1995 или 1996 соответственно) и тестовый балл очередного претендента.

Формат выходного файла

Ответ на каждый тестовый набор выводится в отдельной строке. Если хотя бы одно из требований выполнить невозможно, то в качестве ответа следует вывести только число -1. В противном случае соответствующая строка сначала должна содержать минимальное значение величины F, а затем три числа M94, M95 и M96, на которых это минимальное значение достигается, удовлетворяющие всем требованиям отбора. Если искомых вариантов несколько, то разрешается выводить любой из них.

Примеры тестов

№ Входной файл (school.in) Выходной файл (school.out)
1 
3
1 1 1
4
1994 3
1994 4
1996 1
1996 2
1 1 1
3
1995 2
1994 3
1996 1
1 1 1
3
1994 1
1995 2
1996 3
 
-1
0 1 1 1
-1
2 
1
2 3 1
7
1996 2
1994 7
1994 4
1996 1
1995 3
1994 5
1995 6
 
2 3 2 1
0.054s 0.008s 13