yukicoder-596

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/596 No.596 郵便配達] ==

=== Description ===

{{{
#!html
<p>$[0,N)$的每个整点上住着一家人，其中有$M$个邮局，第$i$个邮局位于$x_i$处，每个邮局里面有$d_i$封信，你也知道每封信需要送到哪里去。</p>

<p>现在你可以任意选个起点和终点，问把所有信都送达的最小移动距离。每次你可以拿任意多封信。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$N$ $M$<br>
$x_1$ $d_1$<br>
$y_1$ $y_2$ $y_3$ $\dots$ $y_{d_1}$<br>
$x_2$ $d_2$<br>
$y_1$ $y_2$ $y_3$ $\dots$ $y_{d_2}$<br>
$\vdots$<br>
$x_M$ $d_M$<br>
$y_1$ $y_2$ $y_3$ $\dots$ $y_{d_M}$<br>
</p>
<p>
$1 \leq N \leq 7 \times 10^{6}, 1 \le M \le 5 \times 10^5, 0 \le x_i, y_i < N, 1 \le d_i, \sum d_i \le 10^6$。
</p>
}}}

=== Output ===

{{{
#!html
<p>输出最短移动距离</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
6 1
0 1
1
</pre>
}}}
输出
{{{
#!html
<pre>
1
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
9 4
0 3
2 7 6
6 2
8 5
1 4
2 7 0 1
4 2
1 6
</pre>
}}}
输出
{{{
#!html
<pre>
14
</pre>
}}}

==== Sample 3 ====
输入
{{{
#!html
<pre>
10 3
5 1
1
9 2
0 4
6 3
8 7 2
1 4
2 7 0 1
4 2
1 6
</pre>
}}}
输出
{{{
#!html
<pre>
12
</pre>
}}}

No.596 郵便配達

Description

$[0,N)$的每个整点上住着一家人，其中有$M$个邮局，第$i$个邮局位于$x_i$处，每个邮局里面有$d_i$封信，你也知道每封信需要送到哪里去。

现在你可以任意选个起点和终点，问把所有信都送达的最小移动距离。每次你可以拿任意多封信。

Input

$N$ $M$
$x_1$ $d_1$
$y_1$ $y_2$ $y_3$ $\dots$ $y_{d_1}$
$x_2$ $d_2$
$y_1$ $y_2$ $y_3$ $\dots$ $y_{d_2}$
$\vdots$
$x_M$ $d_M$
$y_1$ $y_2$ $y_3$ $\dots$ $y_{d_M}$

$1 \leq N \leq 7 \times 10^{6}, 1 \le M \le 5 \times 10^5, 0 \le x_i, y_i < N, 1 \le d_i, \sum d_i \le 10^6$。

Output

输出最短移动距离

Sample

Sample 1

输入

6 10 11

输出

1

Sample 2

输入

9 40 32 7 66 28 51 42 7 0 14 21 6

输出

14

Sample 3

输入

10 35 119 20 46 38 7 21 42 7 0 14 21 6

输出

12