• Фермер
  FARMER

Фермер собрал хороший урожай и перед ним встала проблема как можно выгоднее его продать. Фермеру, используя возможности Internet, удалось получить полную информацию о ценах на рынках в соседних селах и цены на горючее. Необходимо написать программу FARMER, которая предложит село, на рынок которого наиболее выгодно отвезти продукцию. У фермера достаточно горючего (которое считается бесплатным), для того, чтобы доехать до любого рынка, но, возможно, необходимо будет купить горючее на обратный путь.

Технические характеристики:

Входные данные: в первой строке текстового файла FARMER.DAT содержатся три числа, разделенные пробелами: количество видов сельхозпродукции N, количество сел K (порядок номеров сел идет сверху вниз, т.е. вначале село с номером 1, затем с номером 2 и т.д.), количество горючего, которое есть у фермера P (0<=N, K, P<=10000). Во второй строке - N целых чисел - количества каждого продукта для продажи. В следующих K строках, которые описывают села - по N+2 целых числа: первое - количество горючего, необходимого на дорогу до этого села в одну сторону, второе - цена на горючее в этом селе, следующие N чисел - цена на соответствующие продукты на рынке.

Выходные данные: в единственной строке текстового файла FARMER.SOL - номер села, в которое нужно везти урожай, или 0 (нуль), - урожай не выгодно везти никуда.

Пример:

FARMER.DAT
3 2 15
1 2 3
5 2 3 2 1
10 3 5 3 5

FARMER.SOL
2