#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
int gain[ 10000 ] ;
class Solution{
public :
int maximumNumberOfOnes( int X, int Y, int S, int M) {
int i;
int j;
int res = 0 ;
for ( i= 0 ; i< ( S) ; i++ ) {
for ( j= 0 ; j< ( S) ; j++ ) {
gain[ i* S+ j] = 0 ;
}
}
for ( i= 0 ; i< ( X) ; i++ ) {
for ( j= 0 ; j< ( Y) ; j++ ) {
gain[ ( i% S) * S + ( j% S) ] ++ ;
}
}
sort( gain, gain+ S* S) ;
for ( i= 0 ; i< ( M) ; i++ ) {
res + = gain[ S* S- 1 - i] ;
}
return res;
}
}
;
// cLay varsion 20190914-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int gain[10000];
//
// class Solution {
// public:
// int maximumNumberOfOnes(int X, int Y, int S, int M) {
// int i, j, res = 0;
//
// rep(i,S) rep(j,S) gain[i*S+j] = 0;
// rep(i,X) rep(j,Y) gain[ (i%S)*S + (j%S) ]++;
// sort(gain, gain+S*S);
//
// rep(i,M) res += gain[S*S-1-i];
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbWFpbiBkdW1teV9tYWluCmludCBtYWluKCl7CiAgcmV0dXJuIDA7Cn0KI3VuZGVmIG1haW4KaW50IGdhaW5bMTAwMDBdOwpjbGFzcyBTb2x1dGlvbnsKICBwdWJsaWM6CiAgaW50IG1heGltdW1OdW1iZXJPZk9uZXMoaW50IFgsIGludCBZLCBpbnQgUywgaW50IE0pewogICAgaW50IGk7CiAgICBpbnQgajsKICAgIGludCByZXMgPSAwOwogICAgZm9yKGk9MDtpPChTKTtpKyspewogICAgICBmb3Ioaj0wO2o8KFMpO2orKyl7CiAgICAgICAgZ2FpbltpKlMral0gPSAwOwogICAgICB9CiAgICB9CiAgICBmb3IoaT0wO2k8KFgpO2krKyl7CiAgICAgIGZvcihqPTA7ajwoWSk7aisrKXsKICAgICAgICBnYWluWyAoaSVTKSpTICsgKGolUykgXSsrOwogICAgICB9CiAgICB9CiAgICBzb3J0KGdhaW4sIGdhaW4rUypTKTsKICAgIGZvcihpPTA7aTwoTSk7aSsrKXsKICAgICAgcmVzICs9IGdhaW5bUypTLTEtaV07CiAgICB9CiAgICByZXR1cm4gcmVzOwogIH0KfQo7Ci8vIGNMYXkgdmFyc2lvbiAyMDE5MDkxNC0xCgovLyAtLS0gb3JpZ2luYWwgY29kZSAtLS0KLy8gI2RlZmluZSBtYWluIGR1bW15X21haW4KLy8ge30KLy8gI3VuZGVmIG1haW4KLy8gCi8vIGludCBnYWluWzEwMDAwXTsKLy8gCi8vIGNsYXNzIFNvbHV0aW9uIHsKLy8gcHVibGljOgovLyAgIGludCBtYXhpbXVtTnVtYmVyT2ZPbmVzKGludCBYLCBpbnQgWSwgaW50IFMsIGludCBNKSB7Ci8vICAgICBpbnQgaSwgaiwgcmVzID0gMDsKLy8gCi8vICAgICByZXAoaSxTKSByZXAoaixTKSBnYWluW2kqUytqXSA9IDA7Ci8vICAgICByZXAoaSxYKSByZXAoaixZKSBnYWluWyAoaSVTKSpTICsgKGolUykgXSsrOwovLyAgICAgc29ydChnYWluLCBnYWluK1MqUyk7Ci8vIAovLyAgICAgcmVwKGksTSkgcmVzICs9IGdhaW5bUypTLTEtaV07Ci8vICAgICByZXR1cm4gcmVzOwovLyAgIH0KLy8gfTsK