题目描述

你成功潜入大使馆并复制了线人所说的文件，但在逃离后，当局已经得知你的行动并封锁了城市。你必须在被抓住之前把数据上传到互联网。

城市中有若干提供免费无线网络的咖啡店。每家店都有自己的营业时间和上传速度，你可能需要在不同咖啡店之间移动。移动过程中不能上传任何数据。

给定需要上传的数据量、各咖啡店的营业时间和网速，以及任意两家咖啡店之间的旅行时间，求最早能够完成全部上传的时刻。

输入格式

• 第一行包含一个整数 $d$（$1\le d\le10^9$），表示需要上传的数据量，单位为 MB。
• 第二行包含一个整数 $n$（$1\le n\le100$），表示咖啡店数量。
• 接下来 $n$ 行，每行包含三个整数 $o_i,c_i,w_i$：
  • $o_i,c_i$（$0\le o_i\le c_i\le24\times60\times60$）分别表示第 $i$ 家咖啡店的开门和关门时刻，单位为秒；
  • $w_i$（$1\le w_i\le1000$）表示该店的上传速度，单位为 MB/s。
• 接下来 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行第 $j$ 个整数 $t_{i,j}$（$0\le t_{i,j}\le24\times60\times60$）表示从第 $i$ 家咖啡店前往第 $j$ 家咖啡店所需的秒数。

你可以选择任意一家咖啡店作为起点，并在它开门时出现在店内。到达一家仍在营业的咖啡店后，可以立即开始上传。

输出格式

输出一个整数，表示能够完成全部数据上传的最早整数时刻，单位为秒。

样例

输入：
200
2
10 20 15
10 40 5
0 5
5 0

输出：
35