当前没有测试数据。

Description

你种了 $n$ 个韭菜，第 $i$ 个韭菜的初始高度是 $a_i$. 由于环境不同，每个韭菜生长速度不一样，第 $i$ 个韭菜会每天长 $v_i$ 高度。韭菜生长被视为在一天的下午瞬间发生。

由于韭菜不停的长，你需要割韭菜，每天上午你都可以选择 $k$ 个韭菜，并割掉 $p$ 长度。若被割的韭菜高度不足 $p$，则视为被割掉了等同于其高度的长度，即割完后高度变为 $0$.

你希望在第 $m$ 天晚上时，最高的韭菜高度尽量矮。求这个高度，并求出如何实现。

Format

Input

第一行四个非负整数 $n,m,k,p\,(1\leq n\leq 10^5,1\leq mk\leq 10^5,0\leq p\leq 10^9)$.

随后 $n$ 行，每行两个正整数 $a_i,v_i\,(0\leq a_i,v_i\leq 10^9)$

Output

第一行一个整数表示最高的韭菜高度。

随后 $m$ 行，每行 $k$ 个正整数，表示你这一天割掉的韭菜编号。无顺序要求，若有多种方案，输出任意一种。

Samples

4 2 2 4
2 7
3 5
10 4
7 4

13
3 4
1 3

Limitation

1s, 256MiB.