​在某日，李老师突然心血来潮决定去虐一虐萌新，于是他找到了萌新LRH，并给了他一道题，如果LRH在2s内无法解答出来，那么李老师就会嘲讽他获取快感。

LRH在0.5s内发现自己没有思路，便在接下来的0.5s内找到了聪明的你，并告诉了你这个题目，希望你能在1s内告诉他答案。

​题目如下：

现在给你一个n×m的矩阵，已知矩阵的第x行第y列上的元素的值是$a*x*x+b*x+c*y$ ，现在问你这个矩阵的第K大元素是多少。

Input

第一行包含三个正整数 n,m,K(1≤n,m≤100000,1≤K≤n×m)，表示矩阵的大小和所询问的第K大。

第二行包含三个整数 a,b,c(−100000≤a,b,c≤100000)，

Output

输出一个整数，表示这个矩阵的第K大。

输入样例 1

3 3 4
1 1 1

输出样例 1

9

输入样例 2

3 3 4
1 1 0

输出样例 2

6

提示

样例1所构成的矩阵如下：

因而矩阵的第4大为9。

样例2所构成的矩阵如下：

因而矩阵的第4大为6。