#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n , m , k , c , a[N] , s[N] , ans;
unordered_map <int , int> f[N];
int g[N];
void Min (int &x , int y)
{
	if (x > y || x == 0)
		x = y;
}
signed main ()
{
	int t;
	cin >> t;
	while (t --)
	{
	cin >> n >> m >> k >> c;
	s[n + 1] = a[n + 1] = 0;
	for (int i = 1;i <= n;i ++)
	{
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	g[1] = a[1] / k * c + a[1] % k , f[a[1] % k] = a[1] / k * c + c;
	for (int i = 1;i <= n;i ++)
	{
		Min (g[i + 1] , g[i] + a[i + 1] / k * c + a[i + 1] % k);
		Min (f[i + 1][a[i + 1] % k] , g[i] + a[i + 1] / k * c + c);
		for (auto it : f[i])
		{
			int x = it.first , y = it.second;
			int tp = min (i + m - 1 , n) , p = k - x , l = i , r = tp , mid;
			while (l < r)
			{
				mid = l + r + 1 >> 1;
				if (s[mid] - s[i] <= p) l = mid;
				else r = mid - 1;
			}
			int nxt = a[r + 1] - p + s[r] - s[i];
			if (r == tp) nxt = a[r + 1];
			Min (g[r + 1] , y + nxt / k * c + nxt % k);
			Min (f[r + 1][nxt % k] , y + nxt / k * c + c);
		}
		g[i] = 0 , f[i].clear ();
	}
	cout << g[n + 1] << '\n';
	g[n + 1] = 0 , f[n + 1].clear ();
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:26:71: error: no match for ‘operator=’ (operand types are ‘std::unordered_map<long long int, long long int>’ and ‘long long int’)
   26 |         g[1] = a[1] / k * c + a[1] % k , f[a[1] % k] = a[1] / k * c + c;
      |                                                                       ^
In file included from /usr/include/c++/14/unordered_map:41,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:188,
                 from answer.code:1:
/usr/include/c++/14/bits/unordered_map.h:279:7: note: candidate: ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(const std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&) [with _Key = long long int; _Tp = long long int; _Hash = std::hash<long long int>; _Pred = std::equal_to<long long int>; _Alloc = std::allocator<std::pair<const long long int, long long int> >]’
  279 |       operator=(const unordered_map&) = default;
      |       ^~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:279:17: note:   no known conversion for argument 1 from ‘long long int’ to ‘const std::unordered_map<long long int, long long int>&’
  279 |       operator=(const unordered_map&) = default;
      |                 ^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:283:7: note: candidate: ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&&) [with _Key = long long int; _Tp = long long int; _Hash = std::hash<long long int>; _Pred = std::equal_to<long long int>; _Alloc = std::allocator<std::pair<const long long int, long long int> >]’
  283 |       operator=(unordered_map&&) = default;
      |       ^~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:283:17: note:   no known conversion for argument 1 from ‘long long int’ to ‘std::unordered_map<long long int, long long int>&&’
  283 |       operator=(unordered_map&&) = default;
      |                 ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:297:7: note: candidate: ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(std::initializer_list<typename std::_Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::value_type>) [with _Key = long long int; _Tp = long long int; _Hash = std::hash<long long int>; _Pred = std::equal_to<long long int>; _Alloc = std::allocator<std::pair<const long long int, long long int> >; typename std::_Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, std::__detail::_Select1st, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Key&> > >::value, false, true> >::value_type = std::pair<const long long int, long long int>]’
  297 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:297:46: note:   no known conversion for argument 1 from ‘long long int’ to ‘std::initializer_list<std::pair<const long long int, long long int> >’
  297 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~