C. Circadian Rhythm
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You would like to make a schedule for your weekend. The weekend consists of two days, Saturday and Sunday, of $$$24\cdot60\cdot60\cdot1000={86\,400\,000}$$$ milliseconds each. You have a list of $$$n$$$ tasks for Saturday and $$$m$$$ tasks for Sunday, and your primary objective is to complete all tasks.

Every task has a start time $$$s$$$, a deadline $$$e$$$, and a duration $$$d$$$, each given in milliseconds. At any moment in time, you are only able to work on a single task. However, you may distribute the work of any task over several periods of time, so long as the total time you work on any task is equal to its duration.

At any moment you are not working on any task, you will sleep. For reasons having to do with your circadian rhythm, you would like to synchronize your sleep schedules on Saturday and Sunday as much as possible. Your secondary objective is thus to maximize the total time overlap of scheduled sleep between Saturday and Sunday.

A schedule for the weekend with perfectly synchronized 8 hours of sleep on each day.
Input

The input consists of:

  • One line with two integers $$$n$$$ and $$$m$$$ ($$$n,m\geq1$$$, $$$n+m\leq{10^{5}}$$$), the number of tasks you need to complete on Saturday and Sunday respectively.
  • $$$n+m$$$ lines, each with three integers $$$s$$$, $$$e$$$, and $$$d$$$ ($$$0\leq s \lt e\leq {86\,400\,000}$$$, $$$1\leq d\leq e-s$$$), the start time, deadline, and duration respectively of each task in milliseconds. The first $$$n$$$ of these lines describe the tasks for Saturday, and the remaining $$$m$$$ lines describe the tasks for Sunday.
Output

If it is impossible to complete all the tasks, output impossible. Otherwise, output the maximum number of milliseconds of overlap of scheduled sleep between Saturday and Sunday.

Examples
Input
1 1
40000000 60000000 15000000
50000000 70000000 15000000
Output
66400000
Input
2 1
40000000 60000000 15000000
40000000 60000000 15000000
50000000 70000000 15000000
Output
impossible
Input
3 2
25000000 55000000 10000000
35000000 45000000 5000000
60000000 75000000 10000000
30000000 40000000 10000000
45000000 65000000 15000000
Output
56400000