На этом шаге рассмотрим постановку задачи "Игра".
Известная компания выпустила игру, для которой необходима конструкция, состоящая из маленьких платформ и труб. Платформы разделяются на стартовые (их N1 штук), финишные (N3 штук) и промежуточные (N2 штук). Все стартовые платформы находятся на одинаковой высоте. Финишные платформы также находятся на одинаковой высоте. Все высоты промежуточных платформ различны. Они меньше высоты стартовых, но больше высоты финишных.
Каждой платформе соответствует уникальный номер от 1 до N1+N2+N3. Нумерация следующая: сначала перечислены все стартовые платформы, затем промежуточные и, наконец, финишные. Все промежуточные платформы пронумерованы по убыванию высоты. То есть если высота промежуточной платформы А больше высоты платформы В, то номер А меньше номера В.
На каждой из стартовых платформ находится шарик. Шарик может скатить ся с платформы А на платформу В, если они соединены трубой и высота А больше высоты В. На каждой из финишных платформ может оказаться не более одного шарика. Если шарик находится на некоторой платформе, то игрок может выбрать направление дальнейшего пути шарика, то есть выбрать платформу, на которую шарик скатится. Также для каждой проме жуточной платформы задано число С, равное максимальному количеству шариков, которые могут прокатиться по ней за время игры. Цель игры заключается в том, чтобы на финишных платформах оказалось как можно больше шариков.
Вам нужно узнать, какое максимальное количество шариков может оказаться на финишных платформах в результате игры.
Ввод:Во входном файле Game.in находится информация о конструкции в следующей форме:
N1 N2 N3
CN1+1
CN1+N2
K1 A[1, 1] : A[1, K1]
K2 A[2, 1] : A[2, K2]
KN1+N2 A[N1+N2, 1] : A[N1+N2, KN1+N2]
где числа N1, N2, N3 — соответственно количество стартовых, промежуточных и финишных платформ. Cj — максимальное количество шариков, которые могут прокатиться по промежуточной платформе с номером j (N+1 ≤ j ≤ N1 + N2) за все время
игры. Ki — количество труб, выходящих из платформы с номером i (1 ≤ i ≤ N1 + N2).
Элементы массива A, перечисленные в строке, являются номерами платформ, на
которые может скатиться шарик с соответствующей платформы.
Oграничения:
Все числа на вводе целые:
0 < N1, N2, N3 < 51
1 < N1 + N2 + N3 < 201
0 < Cj < 50
Не существует труб между стартовыми платформами.
Не существует труб между финишными платформами.
Вывод:
В первой строке выходного файла Game.out должно находиться единственное число, равное максимальному количеству шариков, которые могут оказаться на финишных платформах в результате игры.
| Пример ввода | Пример вывода |
| 3 4 3 3 2 1 2 1 4 1 4 1 4 2 5 6 1 7 1 7 3 8 9 10 | 2 |
На следующем шаге рассмотрим решение поставленной задачи.
