#include <bits/stdc++.h>
using namespace std;
#define MAX_W 1000
#define MAX_SCORE (int(1e7))
#define MAX_CALLS (int(1e5))
int N, M, C, S;
vector<int> start, length;
vector< vector< pair<int, int> > > edges;
long long hitCnt, missCnt;
int callCnt, allocCnt;
set< pair<int, int> > cache, lru;
bool rand_roll(int w)
{
return ((long long)(rand())) * MAX_W <= ((long long)(w)) * RAND_MAX;
}
void simulate(int index)
{
if (callCnt == MAX_CALLS) return;
++callCnt;
int address = start[index];
auto it = cache.lower_bound(make_pair(address - S + 1, -1));
while (address < start[index] + length[index])
{
if (it != cache.end() && it->first <= address)
{
++hitCnt;
address = it->first;
lru.erase(make_pair(it->second, it->first));
cache.erase(it);
}
else
{
++missCnt;
if (lru.size() == C)
{
it = lru.begin();
cache.erase(make_pair(it->second, it->first));
lru.erase(it);
}
}
lru.insert(make_pair(allocCnt, address));
it = cache.insert(make_pair(address, allocCnt)).first;
address += S;
++allocCnt;
++it;
}
for (int i = 0; i < edges[index].size(); ++i)
{
auto edge = edges[index][i];
if (!rand_roll(edge.second)) continue;
simulate(edge.first);
}
}
long long score(ifstream& input, ifstream& output, int seed)
{
input >> N >> M >> C >> S;
start.resize(N);
length.resize(N);
edges.resize(N);
for (int i = 0; i < N; ++i) input >> length[i];
for (int i = 0; i < M; ++i)
{
int a, b, w;
input >> a >> b >> w;
edges[a - 1].push_back(make_pair(b - 1, w));
}
srand(seed);
int address = 0;
for (int i = 0; i < N; ++i)
{
int index;
output >> index;
start[index - 1] = address;
address += length[index - 1];
}
hitCnt = missCnt = 0;
callCnt = allocCnt = 0;
for (int i = 0; i < N; ++i) simulate(i);
return (hitCnt * MAX_SCORE)/(hitCnt + missCnt);
}
int main(int argc, char *argv[])
{
if (argc < 3)
{
cerr << "Scorer arguments must be:" << endl
<< " 1) test input file path" << endl
<< " 2) output file path" << endl
<< " 3) [random seed] (optional, default is 0)" << endl;
return 0;
}
int seed = 0;
if (argc == 4) istringstream(argv[3]) >> seed;
auto input = ifstream(argv[1]);
auto output = ifstream(argv[2]);
cout << score(input, output, seed) << endl;
return 0;
}
