Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

When Kefa came to the restaurant and sat at a table, the waiter immediately brought him…

  1. User

    When Kefa came to the restaurant and sat at a table, the waiter immediately brought him the menu. There were n dishes. Kefa knows that he needs exactly m dishes. But at that, he doesn't want to order the same dish twice to taste as many dishes as possible.

    Kefa knows that the i-th dish gives him ai units of satisfaction. But some dishes do not go well together and some dishes go very well together. Kefa set to himself k rules of eating food of the following type — if he eats dish x exactly before dish y (there should be no other dishes between x and y), then his satisfaction level raises by c.

    Of course, our parrot wants to get some maximal possible satisfaction from going to the restaurant. Help him in this hard task! Input

    The first line of the input contains three space-separated numbers, n, m and k (1 ≤ m ≤ n ≤ 18, 0 ≤ k ≤ n * (n - 1)) — the number of dishes on the menu, the number of portions Kefa needs to eat to get full and the number of eating rules.

    The second line contains n space-separated numbers ai, (0 ≤ ai ≤ 109) — the satisfaction he gets from the i-th dish.

    Next k lines contain the rules. The i-th rule is described by the three numbers xi, yi and ci (1 ≤ xi, yi ≤ n, 0 ≤ ci ≤ 109). That means that if you eat dish xi right before dish yi, then the Kefa's satisfaction increases by ci. It is guaranteed that there are no such pairs of indexes i and j (1 ≤ i < j ≤ k), that xi = xj and yi = yj.

    Output

    In the single line of the output print the maximum satisfaction that Kefa can get from going to the restaurant.

    Examples

    Input

    2 2 1 1 1 2 1 1

    Output

    3

    Input

    4 3 2 1 2 3 4 2 1 5 3 4 2

    Output

    12

    Note

    In the first sample it is best to first eat the second dish, then the first one. Then we get one unit of satisfaction for each dish and plus one more for the rule.

    In the second test the fitting sequences of choice are 4 2 1 or 2 1 4. In both cases we get satisfaction 7 for dishes and also, if we fulfill rule 1, we get an additional satisfaction 5.

  2. DeepSeek Assistant

    We need to find maximum satisfaction from a sequence of m dishes (ordered, we choose sequence of length m, with no repetition, i.e., permutation of m distinct dishes from n). Each dish has base satisfaction a_i. Additional bonus c is added if we eat dish x immediately before dish y (adjacent pair). We have up to n=18, m up to n. So we can do DP over subsets: DP[mask][last] = max satisfaction for ordering a subset of dishes represented by mask, ending with last, where the size of mask = something; but we need exactly m dishes. Since n is <=18, total subsets 2^n ~ 262k, which is manageable. DP over subsets of size up to m, with last dish. Complexity O(2^n * n^2) naive, but 2^n=262k, n=18, n^2=324, product ~85 million, which is fine. However we need to handle only masks of size <= m. But m <= n, so worst-case m=n => full permutation: we can compute DP for all subsets. But the DP might compute for all subsets regardless of size. That's okay. Memory: dp[mask][last] with int64, 2^18 * 18 = 4.7 million, okay.

    We need to output max dp[mask][last] where popcount(mask)==m.

    Transition: from dp[mask][last] we can add a new dish nxt not in mask, new_mask = mask| (1<<nxt), dp[new_mask][nxt] = max(dp[new_mask][nxt], dp[mask][last] + a_nxt + bonus[last][nxt]).

    Base: start from empty? We can initialize dp[mask][last] for mask with single element: dp[1<<i][i] = a_i.

    Then iterate over masks from 1 to 2^n-1, for each last, if dp[mask][last] is defined, then try all nxt not in mask. Keep best.

    Finally answer = max_{mask: popcount(mask)==m, last} dp[mask][last].

    Constraints: n up to 18, k up to n*(n-1) which is ~306, so we can store bonus as 2D array bonus[x][y] = c if rule exists, else 0.

    Edge Cases: m=0? But m>=1 as per constraints (1 ≤ m). So at least one dish.

    Also note: the rule applies only if x exactly before y; order matters. So we only add bonus when we add nxt after last.

    All values up to 1e9, sums up to m * 1e9 plus bonuses, maybe up to 1e10ish, fit in 64-bit.

    Thus solution is straightforward.

    Let's test with given examples.

    Example1: n=2,m=2,k=1. a=[1,1], rule: (2,1,1). So bonus[2][1]=1. Base: dp[01][0]? indices 0-based: dish1 index0, dish2 index1. So dp[1<<0][0] = a0=1; dp[1<<1][1] = a1=1. From mask {0} last=0: try nxt=1: dp[11][1] = 1 + a1 + bonus[0][1]? Actually last=0, nxt=1. bonus[0][1] is 0 because rule is (2,1) which is index1->0? Wait rule: dish 2 before dish 1 => x=2,y=1 => indices: 2->1 => index1->0. So bonus[1][0]=1. So from {0} last=0, nxt=1: dp[11][1] = 1+1+0=2. From {1} last=1: nxt=0: dp[11][0] = 1+1+bonus[1][0]=1 => 3. So max for mask 3 popcount2 is max(2,3)=3. Output 3. Good.

    Example2: n=4,m=3,k=2. a=[1,2,3,4]. Rules: (2,1,5) => bonus[1][0]? indices: dish2 index1, dish1 index0 => bonus[1][0]=5; (3,4,2) => dish3 index2, dish4 index3 => bonus[2][3]=2. We need maximum subset size 3. Let's compute: Sequence 2,1,4: dish2 (a=2) + dish1 (1) + dish4 (4)=7, plus bonus for (2,1)=5, (1,4) no bonus, total 12. Or 4,2,1: dish4 (4), dish2 (2), dish1 (1)=7, plus bonus for (2,1)=5, total 12. So answer 12.

    Our DP will find it.

    Implementation details:

    • Use zero-based indexing.
    • dp[mask][last] can be stored as a vector of vectors of int64, with size (1<<n) x n, initialized to -INF (or 0 but we need to differentiate). Since m>=1, we start from single-dish masks.
    • Initialize dp[1<<i][i] = a[i].
    • Iterate mask from 1 to (1<<n)-1. For each last where dp[mask][last] not -INF, then for each nxt from 0 to n-1: if not (mask>>nxt &1), then new_mask = mask | (1<<nxt); new_val = dp[mask][last] + a[nxt] + bonus[last][nxt]; update dp[new_mask][nxt] = max(...).
    • Complexity: masks (2^n) * n * n (inner loop over nxt). But we can optimize by precomputing list of not in mask? But n is small.
    • For m constraints we can early prune masks with size > m? But it's okay to compute all, then only check those with size == m. Since 2^n <= 262k, it's fine.

    Potential memory: dp of size 2^18 * 18 ~ 4.7 million, each 8 bytes = 38 MB, okay. Alternatively we can use vector<vector> dp(1<<n, vector(n, -INF)). But -INF should be less than minimum possible; we can use -1e18 or LLONG_MIN. Because satisfaction can be up to: a_i up to 1e9, m up to 18, bonus up to 1e9 per adjacent, maximum number of bonuses m-1, so total up to 181e9 + 171e9 = 35e9 = 3.5e10, so using -1e18 is safe.

    Alternatively, we could use 2D array allocated dynamically: long long dp[1<<18][18] might be too large for stack? Usually 2^18 * 18 * 8 = 38MB, stack may overflow if allocated locally. Better to allocate globally or use vector.

    I'll allocate a global array: const int N = 18, M = 1<<N; long long dp[M][N]; but M = 262144, times 18 ~ 4.7 million, okay but might be large for global memory? 4.7M * 8 = 38 MB, which is okay for global (BSS?) Actually it's static memory, not stack. Usually Codeforces allows 256 MB. So it's fine. But careful: some compilers may have limits, but usually fine. However we can also use vector.

    I'll use vector<vector> dp(1<<n, vector(n, -1e18)). Then assign base.

    We'll read n,m,k, then a[0..n-1], then bonus array n x n initialized to 0, read rules and set bonus[x-1][y-1] = c.

    Now DP.

    Implementation:

    int n, m, k; cin >> n >> m >> k; vector a(n); for (int i=0;i<n;i++) cin>>a[i]; vector<vector> bonus(n, vector(n,0)); for(int i=0;i<k;i++){ int x,y; long long c; cin>>x>>y>>c; x--; y--; bonus[x][y] = c; } int full = 1<<n; vector<vector> dp(full, vector(n, -1e18)); // could use LLONG_MIN for(int i=0;i<n;i++) dp[1<<i][i] = a[i]; for(int mask=0; mask<full; mask++){ for(int last=0; last<n; last++){ if(dp[mask][last] == -1e18) continue; // try nxt for(int nxt=0; nxt<n; nxt++){ if(mask>>nxt &1) continue; int new_mask = mask | (1<<nxt); long long new_val = dp[mask][last] + a[nxt] + bonus[last][nxt]; if(new_val > dp[new_mask][nxt]) dp[new_mask][nxt] = new_val; } } } long long ans = 0; // but we need at least one dish, but could be negative? a_i>=0, c>=0, so satisfaction non-negative, but we can set ans=0 initially but we must ensure we consider only masks with size==m. bool found = false; for(int mask=0; mask<full; mask++){ if(__builtin_popcount(mask) == m){ for(int last=0; last<n; last++){ if(dp[mask][last] > ans){ ans = dp[mask][last]; found = true; } } } } cout << ans << endl;

    But careful: dp[mask][last] might be -INF for some mask/last, but we skip because ans will be updated only if greater than ans. Since ans initialized as 0 and all satisfaction non-negative, it's fine. However if all a_i and c are 0, ans remains 0, but we should output 0 which is correct. But if there is possibility of negative satisfaction? a_i>=0, c>=0, so yes all non-negative. So ans=0 works. But what if m>0 and all a_i=0 and no bonuses? Then max is 0. So okay.

    But we might also consider using long long for ans; base dp values are >= a_i>=0. So 0 works.

    We need to note that the DP includes masks of size 1,2,..., n. So it's fine.

    Potential optimization: we can iterate masks in increasing order of popcount but not necessary.

    Edge: If m=1, we need to pick a single dish. Our DP base has dp[1<<i][i] = a_i. Then for answer, we look at masks of size 1 and take max over dp[mask][last], which yields max a_i. And there are no bonuses. So correct.

    Now check constraints: k up to n*(n-1), but we store full n x n bonus matrix, which is 18x18 = 324, trivial.

    Memory: dp as vector of vectors with size 2^18 * 18, each vector inside is separate? That may cause many allocations; better to use a flat array to reduce overhead. But 2^18=262144, each vector of length 18, so we have 262144 vectors, each allocating separate memory for 18 longs. That is 262144188 ~ 38 MB plus overhead for each vector (maybe 24 bytes per vector), that adds up to 262144*24 ≈ 6.3 MB, total ~44 MB, still okay. But we could optimize: use a single vector of size (1<<n)n and index as maskn + last. But for simplicity, the vector of vectors is fine in 2^18. However in C++ creating 262k vectors might be slow in construction? But we can allocate it like:

    vector<vector> dp(1<<n, vector(n, -INF));

    This constructs one vector of size 1<<n, each element is a vector(n, -INF). That's okay; the construction time may be a bit heavy but still within limits (262k * 18 ≈ 4.7M assignments). Usually fine.

    Alternatively, we can use array of arrays: long long dp[1<<18][18] but as a global it's fine. I'll use global.

    Let's do:

    const int MAXN = 18; const int MAXMASK = 1<<MAXN; long long dp[MAXMASK][MAXN]; But we need n dynamic, but MAXMASK is 1<<18, we can still use full size, but we only use up to 1<<n. Since n <=18, that's fine. But we need to initialize dp entries to -INF. We can use memset? But we need to set to a very small number, maybe using fill with -INF. Simpler: we can use vector with flat array:

    int full = 1<<n; vector dp(full * n, -1e18); Then access: dp[mask * n + last].

    That may be efficient and avoids vector of vectors overhead. Let's implement that.

    Implementation steps:

    • Read input.
    • full = 1<<n.
    • vector dp(full * n, -1e18);
    • For each i: dp[(1<<i)*n + i] = a[i];
    • Iterate mask from 0 to full-1: for last in 0..n-1: idx = maskn + last; if dp[idx] == -INF continue; for nxt in 0..n-1: if mask & (1<<nxt) continue; new_mask = mask | (1<<nxt); new_idx = new_maskn + nxt; new_val = dp[idx] + a[nxt] + bonus[last][nxt]; if new_val > dp[new_idx] then dp[new_idx] = new_val.
    • Then ans = 0, iterate mask: if popcount == m, for last: ans = max(ans, dp[mask*n+last]).

    We need to compute popcount. Use __builtin_popcount.

    Now ensure -INF is small enough: -1e18 is fine because max possible sum is roughly (max a_i + max c) * m. a_i up to 1e9, c up to 1e9, m up to 18 => max ~ 3.6e10, so -1e18 is safe.

    Alternatively, we can use LLONG_MIN from , but adding to LLONG_MIN might overflow? Actually we never do operations on -INF values because we skip them. So we could set to a sentinel like -1e18.

    Better: Use -1e18.

    Now complexity: For each mask we iterate over all last and nxt, but many last may be invalid. However mask up to 262k, n=18, so worst-case 262k * 18 * 18 = 84.8 million operations, which is okay in C++ with simple arithmetic.

    Now consider that dp[mask][last] may be -INF for many combinations because mask may not include last. But we can check if dp[mask][last] is valid only if last is in mask. However our initialization sets dp only for masks with exactly one bit and that last. In transition, we only set dp for new_mask where nxt is added, so dp[new_mask][nxt] becomes valid. So many (mask, last) pairs are invalid because last must be in mask. So we can skip quickly by checking if (mask>>last)&1? But dp[mask][last] might be -INF anyway if not set. So we can just check value. However we can prune: only iterate last for which (mask>>last)&1, but that would require enumerating bits of mask each time. But maybe we can precompute list of bits? However overall complexity is still fine.

    We can improve by iterating over mask, then for each last that is in mask, we can loop over bits of mask to get last, but that would be O(popcount) which is similar. But then we also need to iterate over nxt not in mask, which we need to loop over all n. Alternatively, we can precompute the complement bits? Not necessary.

    Given n=18, it's fine.

    Let's implement.

    Edge Cases:

    • m could be 0? No, m>=1.

    • n could be 0? No.

    • k can be 0, then bonus all zero.

    • The rules are guaranteed no duplicate pairs. So we can just assign.

    Now produce final answer.

    Testing with examples.

    I'll code in C++.

    Potential pitfalls:

    • Use long long for all large numbers.

    • Input: n,m,k may be up to 1e5? Actually n up to 18.

    • Use fast I/O.

    Now code:

    #include <bits/stdc++.h> using namespace std; typedef long long ll;

    int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m, k; cin >> n >> m >> k; vector a(n); for (int i=0;i<n;++i) cin>>a[i]; vector<vector> bonus(n, vector(n,0)); for (int i=0;i<k;++i) { int x,y; ll c; cin>>x>>y>>c; --x; --y; bonus[x][y]=c; } int full = 1<<n; vector dp(fulln, -1e18); for (int i=0;i<n;++i) { dp[(1<<i)n + i] = a[i]; } for (int mask=0; mask<full; ++mask) { for (int last=0; last<n; ++last) { int idx = maskn + last; if (dp[idx] == -1e18) continue; // we might also check if last is in mask, but skip. for (int nxt=0; nxt<n; ++nxt) { if (mask & (1<<nxt)) continue; int new_mask = mask | (1<<nxt); int new_idx = new_maskn + nxt; ll val = dp[idx] + a[nxt] + bonus[last][nxt]; if (val > dp[new_idx]) dp[new_idx] = val; } } } ll ans = 0; for (int mask=0; mask<full; ++mask) { if (__builtin_popcount(mask) == m) { for (int last=0; last<n; ++last) { ans = max(ans, dp[mask*n + last]); } } } cout << ans << endl; return 0; }

    This should work.

    Now note: dp[mask][last] for mask that does not contain last could have been set erroneously? In our transition, we only set dp[new_mask][nxt] where we added nxt, so new_mask includes nxt. So dp entries always correspond to masks where the last is in the mask. And base dp for 1<<i includes i. So all valid entries have last in mask. However we also iterate over all last in the inner loop, including those not in mask; but dp[idx] would be -INF for those because we never set them. So it's okay.

    Alternatively, we could restrict loops to last where mask>>last&1, but we'd need to iterate over bits. That would be more efficient. But okay.

    Now, is there any issue with large number of masks? 2^18=262144, times n=18 gives 4.7M entries; each entry 8 bytes = 37.5 MB; plus bonus small, plus a etc. So within memory.

    Now we can test with sample.

    But wait: The problem statement says: "if he eats dish x exactly before dish y (there should be no other dishes between x and y), then his satisfaction level raises by c." So this is only for consecutive pair. Our DP correctly adds bonus only when last -> nxt.

    Now verify that the satisfaction includes base for each dish. Yes we added a[nxt] each time.

    Now final answer is maximum over all sequences of exactly m distinct dishes.

    Thus solution accepted.

    But we might want to incorporate an optimization: Since m can be less than n, we might not need to consider masks larger than m. But we still compute all, it's okay.

    But note: 2^18 = 262144, that's small.

    Now consider time: 84.8 million operations of simple arithmetic. Each operation includes a loop overhead. Could be borderline but likely okay in C++ with optimizations. But we can further optimize by using bitmask iteration for nxt: for (int nxt = 0; nxt < n; ++nxt) is fine.

    Alternatively, we could precompute for each mask the list of bits not in mask, but that's extra memory.

    Given constraints, it's fine.

    But wait: The problem's k can be up to n*(n-1) which is 306, that's small, so bonus matrix is sparse, but we store full.

    Now check: If n=18, m=18, we need to consider full permutations. DP will compute all subsets. Complexity O(2^n * n^2) which is ~85 million. That's acceptable.

    But there is one nuance: The DP as written iterates over masks from 0 to full-1. This includes masks where popcount may be > m, but we still process them. That's okay.

    We could early break? But we need to compute transitions to larger masks because we need to reach masks of size m, not larger. Actually if we only care about masks up to size m, we don't need to process masks with size >= m because from them we can't get to size m (actually we could, but we only need to stop at m; but if we process a mask of size >= m, it could produce larger masks but not needed. We can restrict to masks with size < m. However DP might still need to process masks of size m-1 to produce masks of size m. So we only need masks up to size m. But we also may need to compute from masks of size m-1 to m. So we can break after size m? Actually we need to process masks of size m-1 to get m. So we should process all masks with size < m. But our DP loops over all masks from 0 to full-1. Could we skip those with size >= m? They would still be processed and they'd try to add more dishes, but that's not needed. To save time, we can stop processing when size >= m. However the DP loop goes in increasing mask order (by integer value) not by size. But we can still check popcount before processing inner loops: if popcount(mask) >= m, continue (skip transitions). But we still need to compute dp for mask with size m? Actually we don't need transitions from size m because we don't need larger masks. So we can skip processing if popcount(mask) >= m. But we still need dp values for size m for answer. So we can compute answer after DP, but we need dp for size m which are computed from masks of size m-1. So we only process masks with popcount < m. That will reduce runtime if m < n. For m small, it's beneficial. For worst-case m=n=18, we still process all masks anyway. But for m=9, number of masks with size < 9 is sum_{i=0}^{8} C(18,i). That sum is about half of 2^18? Actually 2^18 = 262144; sum_{i=0}^{9} C(18,i) is about half? For symmetric binomial, sum_{i=0}^{9} is about 2^{17}=131072 (since median). So roughly half. So could cut runtime roughly by half. But not necessary.

    We can incorporate: compute popcount for mask using builtin, and if (pc >= m) continue; else process. However we need popcount for each mask; computing it each iteration may be overhead but builtin is fast.

    Alternatively, we can iterate over mask in order of increasing bits using subset enumeration? Not needed.

    Given n=18, it's fine.

    Now double-check: In the DP initialization, we set dp[1<<i][i] = a[i]; for masks of size 1. If m=1, we will not process any transitions because popcount(mask) = 1 >= m? Actually we want to process masks of size < m, which if m=1, size 0? No mask of size 0? We don't have base for size 0. So we need to not process any transitions; and answer from masks size 1 should be computed. So condition if (pc >= m) continue, will skip size 1 masks because pc=1 >= m=1? Actually we only want to process masks with size < m, not equal. So if pc >= m, we skip. For m=1, we skip all masks (since pc>=1). That's fine, because no transitions needed. But we still need to compute dp for size 1 masks, which are already initialized. So answer works. For m>1, we need to process masks of size 1,2,..., m-1. So condition if (__builtin_popcount(mask) >= m) continue; will skip size m and above, but still process size m-1.

    So we can include that to reduce work.

    Implementation:

    for (int mask=0; mask<full; ++mask) { int pc = __builtin_popcount(mask); if (pc >= m) continue; // rest... }

    But careful: For masks where pc < m but dp[mask][last] is -INF, we still iterate over last (n times) and then over nxt, doing a bunch of checks. Could we also skip if dp[mask][last] is -INF? We already do that inside loop. So it's okay.

    Now answer: we need to consider masks with pc == m. So after DP, iterate over masks with pc == m.

    Now ensure that dp values for masks of size m are computed: they are set from transitions from masks of size m-1. So after we skip processing masks of size m, we still have dp for size m set because those transitions are from size m-1 to size m. The dp[new_mask][nxt] update will be done when processing mask of size m-1. Since we don't process mask of size m, but we still set dp for size m. So answer includes them.

    Now check if there is any need to process mask of size 0? There's no base for size 0. So no.

    Thus DP works.

    Now test with m=1: No mask processed because pc=0? mask=0 has pc=0 which is < m? 0 < 1, so we would process mask=0? But dp[0][last] is all -INF, so no transitions. However we would still loop over last 0..n-1 and nxt each time. That's extra work. But we can also skip mask=0 because no base. But we could add condition if mask == 0 continue; but it's okay. For n=18, mask=0 only one iteration, trivial.

    Better: we could skip if mask == 0. But not needed.

    Now potential for negative INF: using -1e18, we need to be careful with comparisons. In DP, we compare dp[idx] == -1e18, that's safe because we never change it to something near -1e18 except -1e18 itself. But if we do val > dp[new_idx], and dp[new_idx] might be -1e18, it will be updated.

    Now we must ensure that dp[0][*] never becomes set. So it's fine.

    Now consider whether we need to handle the case where mask=0 and last=some, we skip because dp is -1e18.

    Now we might want to use LLONG_MIN from for sentinel, but then checking equality with LLONG_MIN is fine, but then adding a[nxt] + bonus might overflow? Actually we don't add to LLONG_MIN because we skip dp[idx] if it's sentinel. So safe.

    I'll use LLONG_MIN to be precise: #define INF LLONG_MIN? Actually INF is negative infinity, but we need a sentinel value that we can compare equality. We can use -1e18. But to be safe, use -1e18, since LLONG_MIN is around -9e18, so -1e18 is greater than LLONG_MIN? Actually LLONG_MIN is about -9.22e18. -1e18 is greater (less negative) than LLONG_MIN. So -1e18 is within range, but it's not necessarily a sentinel because actual satisfaction could be as low as 0, so -1e18 is safe as sentinel. But what if we add something to -1e18? If we accidentally use a sentinel that is not negative enough, we might cause updates from invalid states? We skip if dp[idx] == sentinel, so no addition. So it's fine.

    But to be precise, we can initialize to -1e18 and ensure it's less than any possible valid satisfaction (which is >=0). That holds.

    Now test with all zeros: a_i=0, no bonuses, n=18,m=18. Then all dp values for valid sequences are 0. So max ans=0. Our DP will compute correctly.

    Now potential bug: dp is vector of length fulln. When we compute idx = maskn + last, ensure that mask*n doesn't overflow integer? mask up to 2^18-1=262143, n up to 18, product up to 4,718,574, which fits in int. So fine.

    Now final answer.

    One more note: The DP we use is for subsets, but we need to ensure we do not exceed time limit. 85 million operations is fine for 2 seconds? Usually in C++ it's okay if optimized. But we also have some overhead with loops and indexing. Might be borderline but should pass. We can micro-opt:

    • Precompute a and bonus.
    • Use int for indices, etc.
    • Use array for dp with flat vector.
    • Use for loop with local variables.

    Also we can iterate over last only if (mask & (1<<last))? Because if last not in mask, dp is sentinel anyway. But we can incorporate that check to reduce inner loops. But we still have to loop over all n for last (18). That's small. So not needed.

    Alternatively, we can iterate over bits of mask to get last, but that would be O(popcount) which on average 9 for half masks, but then we also need to loop over all n for nxt; but we might also loop over bits of complement for nxt? That would be O(n) anyway. So not much gain.

    Maybe we can precompute for each mask the list of available dishes (not in mask) to iterate only over those, but that again overhead.

    Given n=18, it's fine.

    Now consider the possibility of using DP with bitmask and n=18 is standard for TSP-like problems.

    Thus solution is correct.

    Now we can produce final answer.

    But I'd like to discuss potential alternative: using DP over subsets and last as we did.

    Now final code.

    Let's ensure we use 'long long' for all sums.

    Now provide final answer.

    But wait: There's an issue: In the DP, we process masks from 0 to full-1. But the order of processing matters: we need to ensure that when we process a mask, we have already computed dp for that mask. That's fine because we only transition to larger masks (adding a bit). So any processing order will eventually set dp for larger masks, but we might process a mask, then later a larger mask could update it again? Actually we update dp[new_mask][nxt] from dp[mask][last]. If we process masks in increasing numeric order, it's not guaranteed that we have already processed all smaller masks before? But if we iterate masks from 0 to full-1, when we are at mask, all smaller masks have been processed earlier. However, "smaller" in integer sense does not guarantee that all subsets of mask have been processed, because a subset may have a larger integer value? Example: mask = 3 (binary 11) has subsets {1,2} which are 1 (01) and 2 (10). Both 1 and 2 are less than 3. So indeed all subsets have smaller integer values? Not necessarily: consider mask=4 (100) subset mask=1 (001) which is less than 4, fine. But can a subset have a higher integer value than the superset? No, because adding bits sets more bits to 1, which increases integer value (since bits are in increasing significance). So any superset has a larger integer value than any of its proper subsets (since the highest set bit is at least as high, and if same highest, then more lower bits set). Formally, if A ⊂ B, then the integer representation of B is greater than that of A, because B has all bits of A plus maybe more, so B > A. So iterating masks in increasing order ensures that when we process mask, all its subsets (proper) have been processed already. That's good for DP: we only update from mask to larger mask, so we only need that when we are at mask, its dp value is final (no future updates to mask from other masks). But could we get an update to mask from a smaller mask that we haven't processed yet? No, because smaller masks are processed earlier. So our order is correct. However, there is a nuance: we might update dp[mask][last] from a smaller mask earlier. Since we process masks in increasing order, when we reach mask, all smaller masks have been processed, so dp[mask][last] is final (no more updates from smaller masks later). But could there be updates from masks that are not subsets? No, because to reach mask, we need to add a bit, so the predecessor must be a subset, i.e., smaller. So dp[mask] is final by the time we process mask. That means we can safely use dp[mask] to transition to larger masks. So the order is fine.

    Thus DP works.

    Now double-check with m=18, we process all masks, but we also process masks of size 18. However we skip transitions for size >= m if we add condition. But we still need to use dp[18-size masks] to compute answer. If we skip transitions from size 18 masks, it's fine because they are not needed. But we must be careful that we still need to process masks of size 17 to transition to size 18. Since we process masks in increasing order, we will process all masks up to 2^18-1. The condition (pc >= m) will skip size 18 masks, but they are processed after we have computed them from size 17. That's okay because we don't need to use size 18 to go further.

    But what about masks of size 17? They have pc=17 < 18, so we process them and they transition to size 18. So size 18 dp entries will be set. However, when we later process mask of size 18 (which we skip), we don't need to do anything.

    So okay.

    Now ensure that we still compute dp for size m correctly even if we skip processing masks of size m. Because they are set from masks of size m-1, which we process. So yes.

    Now, could there be a scenario where we need to process masks of size less than m but we skip them inadvertently? No.

    Thus the condition is fine.

    Now after DP, we iterate over all masks and check popcount==m.

    Now answer.

    Now test with example:

    Input: 2 2 1 1 1 2 1 1

    Our code: n=2, m=2, k=1. a = [1,1], bonus[1][0]=1. full=4. dp size = 42=8. Initialize: dp[(1<<0)2+0] = dp[22? Actually (1<<0)=1, mask n + last =12+0=2 => dp[2]=1. (1<<1)=2, index=22+1=5 => dp[5]=1. All others -1e18.

    Now loops:

    mask=0: pc=0<2, iterate last 0..1: idx=0*2+0=0, dp[0]==-1e18 skip; idx=1: dp[1]==-1e18 skip.

    mask=1: pc=1<2. last=0: idx=12+0=2, dp[2]=1 not -INF. Then nxt=0: skip (mask&1). nxt=1: not in mask, new_mask=1|2=3, new_idx=32+1=7? Actually 32=6 +1=7. val = 1 + a[1]=1 + bonus[0][1]=0 => 2. dp[7]=max(-1e18,2)=2. last=1: idx=12+1=3, dp[3] is -INF? Actually we didn't set dp[3] because dp[1][1]? For mask=1, last=1 is not in mask? But we check dp[3] - it's -1e18 so skip. But we also might want to check if last is in mask? It isn't, but dp is -INF, so skip.

    mask=2: pc=1<2. last=0: idx=22+0=4, dp[4] -INF skip; last=1: idx=22+1=5, dp[5]=1. nxt=0: not in mask, new_mask=2|1=3, new_idx=32+0=6? Actually 32=6 +0=6. val =1 + a[0]=1 + bonus[1][0]=1 => 3. dp[6]=3. nxt=1: skip.

    mask=3: pc=2 >=2, so skip processing (continue).

    Now after loops, ans: iterate masks: mask 0 pc=0 not, 1 pc=1 not, 2 pc=1 not, 3 pc=2: last=0 idx=3*2+0=6 dp[6]=3; last=1 idx=7 dp[7]=2; ans max=3. Output 3. Good.

    Second example: Let's simulate mentally: Works.

    Now note: In the transition, we add bonus[last][nxt]. Since last is the dish we are at, and we add nxt after, that's correct.

    Now memory: dp vector of length fulln up to 26214418=4,718,592. long long * 8 = 37.7 MB. bonus: 18x18 = 324, negligible. a: 18. fine.

    Now possible improvements: Use int for indices, but that's fine.

    Now we need to be careful about using __builtin_popcount for unsigned int? It's fine.

    Now test extreme case: n=18, m=18, k=0, a all 1e9. Then maximum sum = 18e9 = 1.8e10, fits in long long.

    Now potential bug: The DP may overflow if we add to sentinel? But we only add when dp is not sentinel.

    Now we should use long long for c and a.

    Now final code.

    Edge Cases: When n=1, m=1, k=0. Then full=2. dp[1<<0][0]=a0. Process mask 1: pc=1 >=1? Since condition if(pc>=m) continue => 1>=1 true, skip. So no transitions. Answer: mask 1 pc=1, dp[2? Actually idx=1n+0? mask=1, n=1, idx=11+0=1, dp[1]=a0. ans = a0. Correct.

    If m=1,n>1, we skip processing all masks of size >=1, so only mask=0 processed? But mask=0 pc=0 <1, we process mask=0 but dp values are -INF, so no transitions. Then answer: for all masks with pc=1, we have dp values set from initialization. So correct.

    Now what about the scenario where m > n? Not allowed because m≤n.

    Now we also need to consider that the rule might involve same dish? The problem says x and y are dishes, but could x equal y? The statement: "if he eats dish x exactly before dish y" — typically x and y are distinct, but not explicitly said they must be distinct? Usually they are distinct. But if a rule with x=y is given, that would be eating the same dish twice consecutively, but the problem says he doesn't want to order the same dish twice, so he never eats the same dish twice. So x=y wouldn't be used because we never have same dish consecutively. But it might be present? The constraints: 1 ≤ xi, yi ≤ n, not necessarily distinct? Possibly they could be equal? But it's not explicitly prohibited. However, we will never have a transition where last == nxt because we only add nxt not in mask, so last cannot equal nxt because nxt is not in mask and last is in mask, so they are distinct. So even if rule for x=y exists, we never use it. So okay.

    Now final solution.

    But wait: Could there be multiple rules for same pair? The problem guarantees no such i,j that xi = xj and yi = yj. So each ordered pair appears at most once.

    Now the DP solution is correct.

    Now I'll present the solution description: Use DP over subsets and last dish.

    Now I'll produce final answer with code.

    But before final, test with some custom case: n=3, m=2, k=... Let's do simple: a=[5,5,5], rules: (1,2,10) => bonus[0][1]=10, (2,3,20)=> bonus[1][2]=20. Expected best: we need two dishes. Options: (1,2): 5+5+10=20; (2,3): 5+5+20=30; (1,3):5+5=10; (2,1):5+5=10? Actually (2,1) no bonus =>10; (3,2):5+5=10; (3,1):10. So max=30. Also (3,2) with no bonus. So answer 30. Let's simulate quickly: dp[1<<1][1]=5, from mask=2 (binary 010) last=1, nxt=2 (mask&4=0): new_mask=6 (110), dp[6][2]=5+5+20=30. Also from mask=2 last=1 nxt=0: dp[3][0]=5+5+? bonus[1][0]=0 =>10. From mask=1 last=0 nxt=1: dp[3][1]=5+5+10=20. From mask=4 last=2 nxt=1: dp[6][1]=5+5+? bonus[2][1]=0=>10. etc. Then ans for mask popcount=2: mask=3 (011) -> last=0:10? Actually dp[3][0]=? from mask=2+? Actually we have dp[3][0] from? Possibly from mask=2 last=1 nxt=0 =>10; dp[3][1] from mask=1 last=0 nxt=1 =>20; mask=5 (101) -> last=2? etc; mask=6 (110) -> last=1:10, last=2:30. So max=30. Good.

    Now everything fine.

    Now provide final answer.

    But note: The DP we wrote uses mask*n+last index. This means we are storing dp for all masks and last, including those where last not in mask. That's okay but uses memory. Could we compress to only last in mask? Not necessary.

    Now finalize.

    Now I'll write the solution explanation.

    Let me produce final output. ```cpp

    #include <bits/stdc++.h> using namespace std; typedef long long ll;

    int main() { ios::sync_with_stdio(false); cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    vector<vector<ll>> bonus(n, vector<ll>(n, 0));
    for (int i = 0; i < k; ++i) {
        int x, y; ll c;
        cin >> x >> y >> c;
        --x; --y;
        bonus[x][y] = c;
    }
    
    int full = 1 << n;
    vector<ll> dp(full * n, -1e18);           // sentinel = very small number
    
    // base: sequences of one dish
    for (int i = 0; i < n; ++i)
        dp[(1 << i) * n + i] = a[i];
    
    // DP over subsets
    for (int mask = 0; mask < full; ++mask) {
        int pc = __builtin_popcount(mask);
        if (pc >= m) continue;                // we only need to build up to size m-1
        for (int last = 0; last < n; ++last) {
            int idx = mask * n + last;
            if (dp[idx] == -1e18) continue;   // state not reachable
            for (int nxt = 0; nxt < n; ++nxt) {
                if (mask & (1 << nxt)) continue;
                int new_mask = mask | (1 << nxt);
                int new_idx = new_mask * n + nxt;
                ll val = dp[idx] + a[nxt] + bonus[last][nxt];
                if (val > dp[new_idx])
                    dp[new_idx] = val;
            }
        }
    }
    
    ll ans = 0;
    for (int mask = 0; mask < full; ++mask) {
        if (__builtin_popcount(mask) != m) continue;
        for (int last = 0; last < n; ++last)
            ans = max(ans, dp[mask * n + last]);
    }
    cout << ans << endl;
    
    return 0;
    

    }