求助一道题

意思大概是一开始有x点战力，现在给你n+m个选择，你只能选择其中k个，其中前n个选择后战力加ai，后m个选择后战力乘ai，求获得的最大战力，答案对998244353 取模

数据

n和m小于10^5,保证每个选项ai都是整数

我写了个背包超时了，求助

#include<bits/stdc++.h>
using namespace std;
long long x,n,m,k;
long long f[1000000];
long long a[1000000];
const long long inf=998244353;
int main(){
    cin>>x>>n>>m>>k;
    f[0]=x;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
    }
    for(long long i=n+1;i<=n+m;i++){
       cin>>a[i];
    }
    for(long long i=1;i<=n+m;i++){
       for(long long j=k;j>=1;j--){
          if(i<=n){ 
             f[j]=max(f[j],f[j-1]+a[i]%inf);
          }else{
             f[j]=max(f[j],f[j-1]*a[i]%inf);
          }
       }
       //out<<i<<" "<<f[k]<<endl;
    }
    cout<<f[k]%inf;
}