ロボットで効率よく物資を回収せよ！
あなたは、与えられたミッションの実現に必要なロボットの開発に成功しました。
ロボットには物資を回収する機構があります。
ロボットは上下左右いずれかの方向に1マスずつ移動でき、移動時に総重量に応じてエネルギーを消費します。
あなたに与えられたミッションは「ロボットを用いて部屋に配置された物資を全て荷台に載せた状態で元の位置の戻ること」です。
このミッションにおいて、ロボットが移動時に消費するエネルギーの最小値を調べて解答してください。

部屋に配置される物資の数は最大で10個までです。

【ロボットの動作】
・上下左右のマスに移動する。（斜め移動はできません。）
・自分のいるマスに置かれた物資を荷台に載せる。
なお、このミッションでは荷台に載せた物資を途中で手放すことは許可されていません。
物資の置かれたマスを素通りすることは可能です。

【部屋の例】

「開始時のロボットの位置(R)、物資の置かれたマス(①～⑨。数字は物資の重さ)、白マス」はすべて通過可能です。
黒マス及び部屋の外への移動は禁止されています。

上図の部屋は下記の文字列で表されます。
"3 4 1X5RX00309X2"
つまり、"横マス数(1桁の数字) 縦マス数(1桁の数字) 一番上から一番下まで各行の左から右に順番に並べられた各マスの情報" という形式です。

各マスの情報を表す文字の意味は以下の通りです。
R: ミッション開始時にロボットの置かれているマス (1箇所のみ)
X: 黒マス
0: 何もないマス(白マス)
1～9: 数値分の重さの物資が1つ置かれたマス (合計10箇所以内)

※ミッション達成が不可能な部屋が入力として与えられることはありません。

ロボットは1マス移動する度に、「運搬している物資の合計の重さ＋ロボットの重さ」の数値分のエネルギーを消費します。
ロボットの重さは1000です。

部屋を表す文字列が入力として与えられます。
3パターンの入力があります。それぞれに対する答えを求め、カンマ区切りで答えてください。

※入力データファイルをダウンロードして解答してください。
配点：400点