L_. Гаджеты за доллары и фунты ограничение по времени на тест2 секунды
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Нура хочет купить k гаджетов. У неё есть s бурлей. В магазине каждый из m гаджетов продается либо за доллары, либо за фунты. Таким образом, каждый гаджет характеризуется типом валюты (и стоимостью в этой валюте), за которую он продается. Тип валюты и цена гаджета в этой валюте не меняются со временем.
Покупки Нура может совершать в течение n дней. Для каждого дня известен курс доллара и курс фунта, то есть известна стоимость конвертации бурлей в доллары и фунты.
Каждый день (от 1 до n) Нура может купить любые из гаджетов по текущему курсу. За день можно покупать произвольное количество гаджетов. Каждый гаджет можно купить не более одного раза за все n дней.
Нуре определить номер наименьшего дня, к концу которого у неё будет k гаджетов. Нура всегда расплачивается бурлями, которые конвертируются по курсу дня покупки. Нура не может купить доллары или фунты, она всегда хранит у себя только бурли. Гаджеты пронумерованы целыми числами от 1 до m в порядке их появления во входных данных.
Входные данные
В первой строке находятся четыре целых числа n, m, k, s (1 ≤ n ≤ 2·105, 1 ≤ k ≤ m ≤ 2·105, 1 ≤ s ≤ 109) — количество дней, общее количество гаджетов, количество гаджетов, которые хочет купить Нура и количество бурлей в распоряжении Нуры.
Во второй строке находятся n целых чисел ai (1 ≤ ai ≤ 106) — стоимость одного доллара в бурлях в i-й день.
В третьей строке находятся n целых чисел bi (1 ≤ bi ≤ 106) — стоимость одного фунта в бурлях в i-й день.
Далее в m строках находятся по два целых числа ti, ci (1 ≤ ti ≤ 2, 1 ≤ ci ≤ 106) — тип гаджета и его стоимость. Если тип гаджета равен 1, то он продается только за доллары и его стоимость указана в долларах. Если тип гаджета равен 2, то он продается только за фунты и его стоимость указана в фунтах.
Выходные данные
Если Нура не сможет купить k гаджетов, в единственной строке выведите число -1.
Если же покупка k гаджетов возможна, в первой строке выведите число d — номер наименьшего дня, к концу которого у Нуры будет k гаджетов. В следующих k строках выведите по два целых числа qi, di — номер гаджета и день в который гаджет был куплен. Все qi должны быть различны, di могут совпадать (то есть в один день Нура может купить несколько гаджетов). Дни пронумерованы от 1 до n. Пары qi, di можно выводить в любом порядке.
Если возможных купить гаджеты за минимальное количество дней d несколько, то выведите любой из них.
Примеры
входные данные
5 4 2 2
1 2 3 2 1
3 2 1 2 3
1 1
2 1
1 2
2 2
выходные данные
3
1 1
2 3
входные данные
4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2
выходные данные
-1
входные данныеСкопировать
4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432
выходные данные
-1
program Proizv;
const
Di = 8; // размерность массива, можно менять на любое другое строки
Dj = 10; // а здесь столбцы
var
A: array [1..Di, 1..Dj] of Integer;
i, j, p: Integer;
begin
Randomize;
for i := 1 to Di do begin
WriteLn;
for j := 1 to Dj do begin
A [i, j] := Random (21) - 3;
Write (A [i, j] :3, ' ');
end;
end;
p := 1;
for i := 1 to Di do begin
if i mod 2 = 0 then // если строка четная то пропускаем
Continue;
for j := 1 to Dj do begin
if A [i, j] < 0 then // перемножаем только отрицательные значения
p := p * A [i, j];
end;
end;
WriteLn;
WriteLn ('Произведение = ', p);
ReadLn;
end.
Объяснение:
для упрощения считаем, что хотя бы одно требуемое число будет найдено. Если таких чисел найдено не будет, то результат произведения будет равен 1.
program array4x4;
const
D = 4; // размерность массива, можно менять на любое другое
var
A: array [1..D, 1..D] of Integer;
i, j, s, smax, jmax, smin, imin: Integer;
begin
Randomize;
for i := 1 to D do begin
WriteLn;
for j := 1 to D do begin
A [i, j] := Random (21) - 5;
Write (A [i, j] :3, ' ');
end;
end;
smax := 0;
jmax := 0;
for j := 1 to D do begin
s := 0;
for i := 1 to D do begin
s := s + Abs (A [i, j]);
end;
if s > smax then begin
smax := s;
jmax := j;
end;
end;
WriteLn;
WriteLn ('Столбец № ', jmax, ' Сумма модулей = ', smax);
imin := 1;
smin := MaxInt;
for i := 1 to D do begin
if A [i, jmax] < smin then begin
smin := A [i, jmax];
imin := i;
end;
end;
WriteLn ('Наименьший элемент: ', imin, ' : ', jmax, ' Равен = ', smin);
ReadLn;
end.