题目描述

贝茜统计到人类拥有很多大学可以去就读，而奶牛们却一个大学也没有．为了解决这个问题，她和她的同伴们建立了一所奶牛大学$\red{Moo}$大学．

为了防止笨牛入学，学校的创立者搞了一个奶牛智力测试$\red{(CSAT)，}$它的分数在区间$\red{[1，}$$\red{2\times 10^9]}$内．$\red{Moo}$大学的学费很昂贵：不是所有奶 牛都能负担．

事实上，大多数奶牛需要一些财政帮助$\red{a(0≤}$$\red{a≤}$$\red{100000)}$．政府不会给奶牛任何资金，所以所有的资金都来自于学校有限的资金，资金总数为$\red{F(0 ≤}$$\red{F≤}$$\red{2×}$$\red{10^9).}$

更糟的是，虽然有$\red{C(N≤}$$\red{C≤}$$\red{100000)}$头奶牛报考，$\red{Moo}$大学却只能接受$\red{N(1≤}$$\red{N≤}$$\red{19999)}$头奶牛，$\red{N}$为奇数．贝茜既要让这$\red{N}$头奶牛享受最大限度的教育资源，又要它们$\red{CSAT}$分数的中位数尽可能高．

这里说一下对于一个奇数个数组成的集合中中位数的概念．例如，集合$\red{3，}$$\red{8，}$$\red{9，}$$\red{7，}$$\red{5}$的中位数是$\red{7，}$因为有两个数小于$\red{7，}$有两个数大于$\red{7}$．

给出每头奶牛的分数和所需的财政补贴数，可以接纳的奶牛数，补助的资金总数，求出中位数最大的可能值．

输入格式

第$\red{1}$行：三个用空格分开的整数$\red{N，}$$\red{C，}$$\red{F.}$

第$\red{2}$到$\red{C+1}$行：每行有两介用空格隔开的整数．

第一个数表示这头奶牛的$\red{CSAT}$分数；第二个整数表示这头奶牛所需的补助数额．

输出格式

仅一行，一个整数即最大的中位数可能值．如不存在输出$\red{-1.}$

样例

输入样例

3  5  70
30  25
50  21
20  20
5  18
35  30

输出样例

35

提示

样例说明

如果贝茜接收$\red{CSAT}$分数为$\red{5，}$$\red{35，}$$\red{50}$的奶牛，中位数为$\red{35.}$总的资金要求为$\red{18+30+21=69}$