暴力贪心的人，会怎样看待1625夹克爷发的红包？

本文共计1331个文字，预计阅读时间需要6分钟。

1625英尺布鲁爷爷送红包+基本时间限制：1秒+空间限制：131072KB+分值：20+难度：3级算法题+现场有n排m列观众，布鲁老大会为每位观众派发普通现金红包，每个红包金额随机。

1625夹克爷发红包

基准时间限制：1秒 空间限制：131072KB 分值:20 难度：3级算法题

现场有n排m列观众，夹克老爷会为每一名观众送出普通现金红包，每个红包内金额随机。

接下来，夹克老爷又送出 最多k组高级红包，每 组高级红包会同时给一排或一列的人派发,每 个高级红包的金额皆为x。

派发高级红包时，普通红包将会强制收回。同时，每个人只能得到一个高级红包。（好小气！）

现在求一种派发高级红包的策略，使得现场观众获得的红包总金额最大。

Input

第一行为n,m,x,k四个整数。