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