Нура хочет купить k гаджетов. У неё есть s бурлей. В магазине каждый из m гаджетов продается либо за доллары, либо за фунты. Таким образом, каждый гаджет характеризуется типом валюты (и стоимостью в этой валюте), за которую он продается. Тип валюты и цена гаджета в этой валюте не меняются со временем.
Покупки Нура может совершать в течение n дней. Для каждого дня известен курс доллара и курс фунта, то есть известна стоимость конвертации бурлей в доллары и фунты.
Каждый день (от 1 до n) Нура может купить любые из гаджетов по текущему курсу. За день можно покупать произвольное количество гаджетов. Каждый гаджет можно купить не более одного раза за все n дней.
Помогите Нуре определить номер наименьшего дня, к концу которого у неё будет k гаджетов. Нура всегда расплачивается бурлями, которые конвертируются по курсу дня покупки. Нура не может купить доллары или фунты, она всегда хранит у себя только бурли. Гаджеты пронумерованы целыми числами от 1 до m в порядке их появления во входных данных.
Выходные данные
Если Нура не сможет купить k гаджетов, в единственной строке выведите число -1.
Если же покупка k гаджетов возможна, в первой строке выведите число d — номер наименьшего дня, к концу которого у Нуры будет k гаджетов. В следующих k строках выведите по два целых числа qi, di — номер гаджета и день в который гаджет был куплен. Все qi должны быть различны, di могут совпадать (то есть в один день Нура может купить несколько гаджетов). Дни пронумерованы от 1 до n. Пары qi, di можно выводить в любом порядке.
Если возможных способов купить гаджеты за минимальное количество дней d несколько, то выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2
|
-1
|
|
3
|
4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432
|
-1
|