Production Line (APCS 2021-11 Advanced)

1.0s 256M

There are \(n\) machines in a row. Machine \(i\) has a value \(t_i\): it needs \(t_i\) units of time to produce one unit of data.

There are \(m\) jobs to complete. Job \(i\) requires every machine located at positions \([l_i, r_i]\) to produce \(w_i\) units of data.

You may rearrange the order of the \(n\) machines before the jobs start. Minimize the total time needed to finish all \(m\) jobs.

Input

The first line contains two positive integers \(n\) and \(m\): the number of machines and the number of jobs.

Each of the next \(m\) lines contains three positive integers \(l_i\), \(r_i\) and \(w_i\), meaning that job \(i\) must be done by the machines at positions \(l_i\) through \(r_i\), each producing \(w_i\) units of data.

The last line contains \(n\) positive integers \(t_1, t_2, \ldots, t_n\).

  • \(1 \le n, m \le 200000\)
  • \(1 \le w_i \le 100\)
  • \(1 \le t_i \le 100\)
  • \(1 \le l_i \le r_i \le n\)

Output

Output the minimum total time.

Scoring

  • 30 points: \(1 \le n, m \le 100\), \(w_i = 1\)
  • 30 points: \(w_i = 1\)
  • 40 points: no additional constraints

Sample Input 1

5 1
2 4 1
1 2 3 4 5

Sample Output 1

6

Sample Input 2

10 3
2 5 6
3 6 4
7 8 1
1 2 3 4 5 6 7 8 9 10

Sample Output 2

117

Source

APCS November 2021, programming problem 3 "Production Line"; also available as ZeroJudge g597.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.