Sachverhalt: A. A._, geboren 1957, lebt seit 2010 mit B._, geboren 1941, in dessen Mietwohnung in Meilen. Sie bezieht seit August 2012 von der Sozialbehörde Meilen (nachfolgend: Sozialbehörde) wirtschaftliche Sozialhilfe. Mit Leistungsentscheid vom 22. August 2014 rechnete die Sozialabteilung der Sozialbehörde im Unterstützungsbudget von A._ einen Konkubinatsbeitrag von Fr. 780.05 vonseiten ihres Partners B._ an. Dieser bezieht als AHV-Rentner Ergänzungsleistungen. Auf Ersuchen der A._ hin überprüfte und bestätigte die Sozialbehörde den Leistungsentscheid vom 22. August 2014 (Beschluss vom 20. November 2014). Hiegegen erhoben A._ und B._ Rekurs, den der Bezirksrat Meilen (BRM) mit Beschluss vom 14. September 2015 abwies. B. Dagegen beantragten A._ und B._ beschwerdeweise, der angefochtene BRM-Beschluss vom 14. September 2015 sei aufzuheben. Die Ergänzungsleistungen zur AHV und die AHV-Rente von B._ seien nicht mehr im Budget der A._ durch Anrechnung eines Konkubinatsbeitrages zu berücksichtigen. Die bereits in Abzug gebrachten Konkubinatsbeiträge seien zwecks Schuldentilgung nachträglich auszubezahlen. Das Verwaltungsgericht des Kantons Zürich wies die Beschwerde mit Entscheid vom 14. Januar 2016 ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragen A._ und B._ die Aufhebung des angefochtenen Gerichtsentscheides. Zudem halten sie an ihren vorinstanzlichen Anträgen fest. Weiter ersuchen sie um Gewährung der unentgeltlichen Rechtspflege. Das Bundesgericht hat die vorinstanzlichen Akten eingeholt und auf einen Schriftenwechsel verzichtet.