Java - задача

Условие задачи

Ограничение времени, с1

Ограничение памяти, МБ64

Общее число попыток отправки15

У HR Маши на столе лежат две стопки резюме, размерами n и m, в каждом из резюме указана зарплата, числа a[0..n-1] для одной стопки, и b[0..m-1] для второй. Нулевой индекс указывает на верхнее резюме в стопке.

Маша устанавливает значение s максимальной суммы зарплат и предлагает очень активному стажеру Саше сыграть в игру:

• - За каждый ход Саша может взять одно верхнее резюме из любой стопки и забрать себе в работу
• - Саша считает сумму всех зарплат из резюме, которые он взял. Он может брать новые резюме из стопок только таким образом, чтобы эта сумма не превышала s
• - Игра заканчивается, если Саша больше не может брать резюме

Нужно выяснить, какое максимальное количество резюме Саша мог бы забрать себе в работу, если бы тоже знал зарплаты, указанные в каждом резюме.

Входные данные (поступают в стандартный поток ввода)

Первая строка – целые числа n, m и s через пробел (1≤n≤10 000, 1≤m≤10 000, 1≤s≤200 000 000)

Далее максимальное из n и m (max(n, m)) строк, на каждой из которых один из вариантов:

• - два целых числа a и b через пробел (1≤a≤10 000, 1≤b≤10 000),
• - a и символ - через пробел (1≤a≤10 000)
• - символ - и b через пробел (1≤b≤10 000)

Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются

Выходные данные (ожидаются в стандартном потоке вывода)

Одно целое число, максимальное количество резюме

Пример 1

Ввод:

3 4 11

1 1

2 2

3 3

- 4

Вывод:

5

Пример 2

Ввод:

5 5 10

5 1

1 3

1 3

1 3

1 3

Вывод:

6

Пример 3

Ввод:

6 4 10

4 2

2 1

4 8

6 5

1 -

7 -

Вывод:

4

Примечания по оформлению решения

Возможно использование только стандартных библиотек языков, установки и использование дополнительных библиотек невозможны.

При отправке решений на Java необходимо назвать исполняемый класс Main. В решении не нужно указывать пакет.

Примеры работы со стандартными потоками ввода и вывода

в Java можно использовать java.util.Scanner и System.out.println:

Scanner in = new Scanner(System.in);

String line = in.nextLine();

...

System.out.println(result);