#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)

/*
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiooiiiiiiii@o@@ioiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiaa@@aoiiiiaiaaaoaoiiiiaiooiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@aio@@ioiiaoaaooaoiiii@@@aooiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiaiaaaiaaiiaaooai@aii@oaoaaaiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiio@@iiaaoo@@iiio@aai@oii@aiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiaioo@@iiii@aaaiiio@@@@iiii@@iiiiioooiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiio@i@@@@@a@@ooioaiaiioiiioaoioio@oiiaa@a@aaiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@o@@aaaiooaoaaaaioioioioioioiiiioo@@@@ooio@aiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@i@a@a@a@a@a@a@o@iioiiiiiiiiiiiiaa@@@iooaoaoaoao@i@oioioioioioioioioioioioii@aiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiao@o@a@@@aaa@i@iaoaoao@iaa@a@@@@@aaoiiio@a@oooooooaoaoooooaa@iiiioioioioioioioioioiiaoaoiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@o@@@oaaaoaoooaoaoaoaoaoaoaoaoooooooao@o@@@@@iooaooo@o@@@@@@@a@@aoioioooaiioioioioioioai@oiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@o@@aaaoooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoooaoaa@@@ooooo@@ooiiioaiaoioioioioaaioioioioioio@oioiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@i@@aaooooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@o@@@ioo@a@oooiiioioioioioai@iioioioioooaaiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiioo@a@oooooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@i@@@ooo@i@a@oiiioioioioii@oiiioioio@i@iiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@i@@aoooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@a@aoooo@@aaioioioioii@oiiioioioaaooiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@a@@ooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@o@ooooo@@ioioioioioioiiioioii@aiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@a@@ooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@o@ooo@o@@ioiiioioioioioiiao@oiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiioioioai@i@@ooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@aaaoo@@@@ioioioioioioio@@ioiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiai@i@o@@@@@@@a@a@a@@ooooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoooaoooaoaoaoaoaoaoaoaoaoaoaoaoaooo@@@i@a@@ioioioioioioaoaaiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiai@i@a@aaa@iaoaooooooo@aaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoooaoaoaoaoaooo@oaoaoaoaoaoaoaoooaoaoaoaoaoaoaoaoao@@@i@@ioioioioioio@i@iiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiao@@aaooooaoaoaoaoaooo@o@aooaoaoaoaoaoaoaoaoaoaoaoaoaoao@iaaaoaoaoaoaoooaa@@ooaoaoaoaoao@a@iaoaoaoaoaoaoaoao@oai@aiiioioioioio@i@iiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiai@@aoaoaoaoaoaoaoaoao@@aoaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@o@@aoaoaoaoaoaooo@@@@ooaoaoaoooaa@@ooaoaoaoaoaoaoaooo@@@aiiioioioioio@iaoiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiao@@aoaoaoaoaoaoaoaa@oooaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@@@i@@@iooaoaoaooo@a@@@@@a@@@a@@@@@@ooaoaoaoaoaoaoaooo@o@aiiioioioioio@iooiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiii@i@@ooaoaoaooooo@@@iaoaoaoaoaoaoaoaoao@a@oaoaoaoao@i@aiiio@@@iooaoao@o@a@@@@@iooooaooo@@@@@oaoaoao@iaoaoao@i@oiiioioioioio@iooiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiii@o@oaoaoaoaoaoao@@ooaoaoaoaoaoaoaoaooo@@@iaoaoaooo@a@iiiiiai@@aaooaoaoai@@ai@@aoaoooao@a@@aoaoaoaoao@aooaoaaaaiiioioioioioaaaiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiii@i@aooaoaoaoaoaoaa@oooaoaoaoaoaoaoaoao@i@@@oaoaoaoao@@ioioioioai@@aaooaoao@@aoao@@aoaoao@i@@@@ooaoaoao@@aoao@o@iiiioioioioio@iaiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiii@@aoaoaoaoaoaooo@oaaaoaoaooo@iaoaoooao@o@@@@aoaooo@o@oiiioioioiioo@@aaooao@i@aii@i@@ooaooo@@@@@iaoaooo@oaaoo@aaoioioioioioioaaaiiiiiiiiiiiiiiiiiiiii
iiiiiiiiii@i@aaaaoooaoaoaooo@a@iaoaoaooo@@@iao@a@o@@@o@@aaaooo@@ooioioioioioioai@@aaooao@@ioiiaa@@aooo@@oo@aooaoooaa@aoo@@ooiiioioioioiiaaaiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiooaa@@@oooaoaooo@@aoaoaoaoao@a@a@oaooo@@io@@ooao@i@aiiioioioioioioioio@aaaio@@ioioii@o@@oo@@io@aaaooao@i@@ai@@aiiiioioioioii@oaiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiai@aooaoaoao@@aoaoaoaoao@o@aooaoao@@ii@@aoao@o@iiiioioioioioioioiiio@a@a@@aiioioii@o@@@@iiao@@aoaoao@@ai@@aiioioioioioio@aaiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiii@i@aaoaoaoao@@ooaoaoaoao@o@@ooao@i@aiiao@oai@@aiioioioioioioioioioioii@o@aooiiiiiiii@i@@ioii@o@oooao@@ai@@ioioioioioioii@@aiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiii@o@iaoooai@o@oooaoaooo@@io@@aooo@o@oiiio@@@i@oiiioioioioioioioioioioioioii@i@@@@@a@oooiiioioio@@aaao@@oo@@iiioioioioioii@@ioiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiii@aaiaa@@@@aa@aooaoaoaoaaoo@@@ooo@@ooioii@@@@aoioioioioioioioioioioioioio@@aaaiioaioo@@@@ioiiioao@@oo@@ooaaiiioioioioioii@@iiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiio@@@@@iioiiao@ooo@iaoaoaoao@a@@oo@@iiioii@i@@ioioioioioioioioioioioioioioioio@i@oaaaiiiao@@ioioii@oaa@@@iaoiiioioioioioii@@iiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiao@ooo@aooaoaoaaaoaa@o@@iiioiiiiooioioioioioioioioioioioioioiiio@a@@@o@o@@@iii@i@aioioio@@@a@@aiiiioioioioioio@oiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiioo@aoo@aooaoao@aaoai@@@aii@i@o@@@aaiioioioioioioioioioioioioio@o@@@@iiio@@@@ioii@o@iiiiiaoai@@ioioioioioioioai@iiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiai@aoo@aooaooo@@ooiiaa@o@o@oooioiiiiioioioioioioioioioioioioii@@aa@aiooo@a@@@oiiio@@ioioiiii@@ioioioioioioioooaoiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiio@@oo@aooaooo@@aiioiiaa@oiiio@o@@@aooiiioioioioioioioioioioii@@aa@@@@@@@a@i@@iiiiaaaaiiioio@@iiioioioioioio@iioiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiii@@oo@oaoaooo@@ioioai@aiiio@@@@aaaa@@@iioioioioioioioioioioii@aaa@a@@@@@@@i@@ioioio@@iiioai@@iiioioioioioio@oioiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiii@a@i@iaaaooo@@ioioaaooiiaa@@@aiiii@@@@ioioioioioioioioioioio@i@aaa@@@@@a@i@@ioioii@aooioaoaaioioioioioioii@@iiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiaa@oao@aoooo@@ioii@@ioio@@@i@@aa@o@o@o@oiiioioioioioioioioioio@@aa@i@o@i@@@@iiioii@oioii@aooiiioioioioioii@@iiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiioo@@ao@@ooao@@iiio@oiiio@@ao@@@@@@@@aa@aiiioioioioioioioioiiioao@@@a@o@a@@aiioioiiioiiii@@ioioioioioioioio@@iiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiii@aaa@@@iaa@aiiai@oiiio@@aa@a@@@@@@aa@aiiioioioioioioioioioioioaiaa@oaaaiioioioioioioio@@iiioioioioioioaiaaiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiii@i@@@@@aaaaaiiaiaaiiio@i@@@i@@@@@o@o@aiiioioioioioioioioioioioioiiiiiiioioioioioioiioo@aiiioioioioioioaaiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiio@@@@@@@aaoiiio@aiiioio@@aa@iaa@i@@aaioioioioioioioioioioioioioioioioioioioioioio@i@@aoioioioioioioio@@iiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiaa@@@@@@aaioii@aioioio@i@@@a@a@@@oiiioioioioioioioioioioioioioioioioioioioioii@aaa@@aiioioioioioioio@@iiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@i@@@@ioio@iaoioioiiaiaaaoioioioioioioioioioioioioioioioioioioioioioioioii@@ao@@iiioioioioioioio@aiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiio@@ii@@ioioiiioioioioioioioioioioioioioioioioioioiiiiiiao@iioioioioioioioio@@ao@aiiioioioioioiooo@iiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@@io@aaiioioioioioioioioioioioioioiiioiiiiiiaiaa@a@@@aaoao@@ioioioioioioio@aoo@@iiioioioioioioaaioiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiioo@aooaaioioioioioioioioioioioioioao@o@a@a@aaaaoooooooaiaiaoaaiiioioioioai@aooaaaaiiioioioioii@@iiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@aoo@aioioioioioioioioioioioio@@@oaaaoooaiaioooooooooooooo@aioioioioiooo@ooooo@aioiiioioioai@@aoiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@@@@ooiiioioioioioioioioioio@@aiaioooooooooooooooooooooo@i@iioioioii@i@oooooao@@iiioioioao@a@@ioiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@a@a@aioioioioioioioioioioio@@aioooooooooooooooooooooooooo@aiiioioii@o@oooooao@i@oioioiiaaaaao@aiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiaa@oai@aaoioioioioioioioioioio@@aiooooooooooooooooooooooooai@aiiioio@o@aaoaoooaooo@o@aioio@@aaoo@oooiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@@ooao@i@@ioioioioioioioioioio@@aiooooooooooooooooooooooooai@oioioao@oooaoaoaoaoaooo@i@@@a@@@aoooo@@iiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiio@@aiaoaoooaa@aiiioioioioioioioii@@aiooooooooooooooooooooooooai@oaiiiao@@ooooaoaoaoooooaooo@iaoooaooo@aaiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@iaaooaoaoaoooaa@oioioioioioioioii@oooaiooooooooooooooooooooooai@@ii@@@o@oaoaoaoaoaoaoaoaoaoooooaoaoao@i@aiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiio@@ooaoaoaoaoaooo@i@aioiiioioioioioai@oooooooooooooooooooooooai@i@o@o@@aoooaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@aaiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@iaaaoaoaoaoaoaoaoaoao@aaaioiiioioioii@aooooooooooooooooooaiai@i@@@@oo@oaaooooaoaoaoaoaoaoaoaoaoaoaoaoaoao@i@aiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@aaiooooaoaoaoaoaoaoaoooaa@@aaooioiiiiio@@aoaiaiaiaiaiaiaoaa@a@aaoiioo@aaoaoaoaoaoaoaoaoaoaoaoaoaoooaoaoaooo@@iiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@@@o@a@a@iaoaoaoaoaoaoaoooai@a@@@@@a@oaa@o@@@@@a@a@a@a@@@o@iaiiiiiai@@ooooaoaoaoaoaoaoaoaoaoaoaoaoaoooaoao@i@oiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiioio@aaaaoaoaoaoaoaoaoao@i@@@aio@oaa@@aoaa@iaoooaiioiiiiiiioiioo@@ooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaooooo@aioiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiaaaaaoaoaoooaoaoaoai@@@@ioii@@oo@@iiioioioioioioioioioiiao@aooaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaoaooo@aaiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@ooooo@o@aooaooo@a@@ooiiii@@oo@oaaiiioioioioioioiioo@@@oooaoaoaoooaoaoaoaoaoaoaoaoaoaoooooaooo@oaoiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@@@@@@@a@aooao@i@@aaaiiiii@@oooo@o@aooiiiiiiio@i@a@aaoooaoooaooo@oaoaoaoaoaoaoaoaoaoaoaoaooo@aooiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiooaiioio@@ai@i@@ii@@ioiiii@@aooooo@i@a@@@@@@@@@o@iooooaoaoooaoao@@@iaoaoaoaoaoaoaoaoaoaoao@aaoiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@aaa@@io@a@@ioiiii@@aoaoaoaoooaoaoaoooooaoaoaoaoaooo@i@aaiaaooaoaoaoaoaoaoaoaooo@i@oiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiooaaioai@a@aioiiii@a@oooaoooaoaoooaoaoaoaoaoaooooo@i@oiiio@oooaoaoaoaoaoaoaoaooo@oaoiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@@oo@aioiiii@oaa@aooaoooaoaoaoaoaoaoaoooao@a@iiiiiii@oaoaoooaoaoaoaoooaooo@@ioiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@aoo@aioiiii@iooai@aaaaoooaoooaoooaoao@o@oioiiiiiiii@iaaaoaoooaoaoaoaoao@i@oiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@@oooo@aooiiiiaoaoiiiioo@a@a@i@i@i@o@a@oioiiiiiiiiiiiiii@aooaoaoaoaoaoaooo@oaoiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@aooao@aooiiiiooaaiiiiiiiiiiaiooaiiiiiiiiiiiiiiiiiiiiiiiai@aooooaoooaoooao@aiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@o@iaoao@oaoiiiiai@aiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@iaaooooaoaoaoaa@iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiao@aooaoaoaa@iiiiiio@@iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii@aooaoaoaooo@@iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiio@@ooaoaoaoaa@oiiiiii@@iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiai@aooaoao@oaoiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiaaaaaoaoaooo@o@@iiiiii@@iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiioo@a@ioo@@ioiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

*/

int N, K, X, Y;
//-----------------------------------------------------------------
int main() {
    cin >> N >> K >> X >> Y;

    int ans;
    if (N <= K) ans = N * X;
    else ans = K * X + (N - K) * Y;

    cout << ans << endl;
}

Measured memory_bytes: 256